Flatten Binary Tree to Linked List
Given a binary tree, flatten it to a linked list in-place.
For example,
Given
1
/
2 5
/
3 4 6
The flattened tree should look like:
1
2
3
4
5
6
SOLUTION 1:
使用递归解决,根据left是否为空,先连接left tree, 然后再连接右子树。使用一个tail 来记录链的结尾。在递归之前,先将root.left,root.right保存下来。
1 /**
2 * Definition for binary tree
3 * public class TreeNode {
4 * int val;
5 * TreeNode left;
6 * TreeNode right;
7 * TreeNode(int x) { val = x; }
8 * }
9 */
10 public class Solution {
11 public void flatten(TreeNode root) {
12 dfs(root);
13 }
14
15 // return : the tail of the list.
16 public TreeNode dfs(TreeNode root) {
17 if (root == null) {
18 return null;
19 }
20
21 TreeNode left = root.left;
22 TreeNode right = root.right;
23
24 // Init the root.
25 root.left = null;
26 root.right = null;
27
28 TreeNode tail = root;
29
30 // connect the left tree.
31 if (left != null) {
32 tail.right = left;
33 tail = dfs(left);
34 }
35
36 // connect the right tree.
37 if (right != null) {
38 tail.right = right;
39 tail = dfs(right);
40 }
41
42 return tail;
43 }
44 }
View Code