LeetCode - Flatten Binary Tree to Linked List
Problem description
Given a binary tree, flatten it to a linked list in-place.
For example, given the following tree:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
1
/ \
2 5
/ \ \
3 4 6
The flattened tree should look like:
1
\
2
\
3
\
4
\
5
\
6
Analysis
The basic idea is to use recursion to form the tree.
One key point is that you need to append the right subtree to the end of the left tree. Therefore, a tail node should be the return.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
private TreeNode flattenTree(TreeNode node) {
// Handle the null scenario
if (node == null) {
return null;
}
// For a leaf node, we simply return the
// node as is.
if (node.left == null && node.right == null) {
return node;
}
TreeNode l = node.left;
TreeNode r = node.right;
if (l != null){
node.right = l;
node.left = null;
}
//Recursively flatten the left subtree
TreeNode leftTail = this.flattenTree(l);
// If there was a left subtree, we shuffle the connections
// around so that there is nothing on the left side
// anymore.
if (leftTail != null) {
leftTail.right = r;
}
// Recursively flatten the right subtree
TreeNode rightTail = this.flattenTree(r);
// We need to return the "rightmost" node after we are
// done wiring the new connections.
return rightTail == null ? leftTail : rightTail;
}
public void flatten(TreeNode root) {
this.flattenTree(root);
}
}
What to improve
- do the most ugly solution first and then think a elegant solution.