LeetCode - Binary Tree Upside Down
Problem description
Given a binary tree where all the right nodes are either leaf nodes with a sibling (a left node that shares the same parent node) or empty, flip it upside down and turn it into a tree where the original right nodes turned into left leaf nodes. Return the new root.
Example:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Input: [1,2,3,4,5]
1
/ \
2 3
/ \
4 5
Output: return the root of the binary tree [4,5,2,#,#,3,1]
4
/ \
5 2
/ \
3 1
Analysis
The first thought is to use recursion. And I put all my thoughts here to find a framework on how to solve this type of questions.
First, we need to find out what kind of recursion we are going to use. And in this problem, it would be inorder recursion. Since we have to rotate the left side first so that we can do the node and its right avoiding lost information.
Second, you need to find out what we need for each recursion. In this problem, it would be the right child after the rotate, which is the initial root. So we return that root.
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
/**
* 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 {
TreeNode newRoot;
public TreeNode upsideDownBinaryTree(TreeNode root) {
if (root == null){
return null;
}
recursion(root);
return newRoot;
}
TreeNode recursion(TreeNode root){
if (root == null){
return null;
}
if (root.left != null){
TreeNode right = recursion(root.left);
right.left = root.right;
right.right = root;
root.left = null;
root.right = null;
return right.right;
}
else{
newRoot = root;
return root;
}
}
}
Here’s another way to solve it.
An observation is that the even we rotate the left side, we still have the pointer from root to left. So we can use root.left even after the rotate to get the right child after rotation.
1
2
3
4
5
6
7
8
9
10
11
12
public TreeNode upsideDownBinaryTree(TreeNode root) {
if(root == null || root.left == null) {
return root;
}
TreeNode newRoot = upsideDownBinaryTree(root.left);
root.left.left = root.right; // node 2 left children
root.left.right = root; // node 2 right children
root.left = null;
root.right = null;
return newRoot;
}
And for the iteration solution:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public TreeNode upsideDownBinaryTree(TreeNode root) {
TreeNode curr = root;
TreeNode next = null;
TreeNode temp = null;
TreeNode prev = null;
while(curr != null) {
next = curr.left;
// swapping nodes now, need temp to keep the previous right child
curr.left = temp;
temp = curr.right;
curr.right = prev;
prev = curr;
curr = next;
}
return prev;
}