https://leetcode.com/problems/binary-tree-upside-down/
Solution Explanation-space)-and-iterative-solutions-(O(1)-space)-with-explanation-and-figure)
Recursion1
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/**
* 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 TreeNode upsideDownBinaryTree(TreeNode root) {
if(root.left==null&&root.right==null) return root;
/* -->a new way of thinking about recursion<--
* save the substructure before do some actions
* on the current objects.
*/
TreeNode newRoot=upsideDownBinaryTree(root.left);
// actions on the current objects.
root.left.left=root.right;
root.left.right=root;
root.left=null;
root.right=null;
// actions end.
return newRoot;
}
}
Iteration1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20class Solution {
public TreeNode upsideDownBinaryTree(TreeNode root) {
TreeNode curr=root;
TreeNode next=null;
TreeNode prev=null;
TreeNode tmp=null;
while(curr!=null){
next=curr.left;
// swapping nodes now, need temp to keep the previous right child
curr.left=tmp;
tmp=curr.right;
curr.right=prev;
prev=curr;
curr=next;
}
return prev;
}
}