LeetCode 114. Flatten Binary Tree to Linked List

题目

Given a binary tree, flatten it to a linked list in-place.

For example, given the following tree:

1 / \ 2 5 / \ \ 3 4 6

The flattened tree should look like:

1 \ 2 \ 3 \ 4 \ 5 \ 6

---

这道题把一棵树变成全部用right连接的一个链表，刚开始想复杂了，后来才发现其实就是最简单的想法：遍历这棵树，如果当前遍历到的节点有left，那就把left接到right下，然后把原先的right接到新的right的最右下面。刚开始快乐地写好了代码，想着while (curr.left != null)就行了，没想到还有这种情况：1.right = 2, 2.left = 3。然后看了解答发现直接while里面curr就好了，如果curr没有left就继续往右走看看还有没有带left的，如果有left就挪位置。时间复杂度，我想可能还是O(n)吧。

Runtime: 0 ms, faster than 100.00% of Java online submissions for Flatten Binary Tree to Linked List.

Memory Usage: 38.7 MB, less than 19.99% of Java online submissions for Flatten Binary Tree to Linked List.  

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public void flatten(TreeNode root) { TreeNode curr = root; while (curr != null) { if (curr.left == null) { curr = curr.right; continue; } TreeNode right = curr.right; curr.right = curr.left; curr.left = null; TreeNode temp = curr.right; while (temp.right != null) { temp = temp.right; } temp.right = right; curr = curr.right; } } }