BinaryTreeUpsideDown [source code]
public class BinaryTreeUpsideDown {
static
/******************************************************************************/
class Solution {
public TreeNode upsideDownBinaryTree(TreeNode root) {
TreeNode prev = null, gift = null;
while (root != null) {
TreeNode next = root.left;
root.left = gift;
gift = root.right;
root.right = prev;
prev = root;
root = next;
}
return prev;
}
}
/******************************************************************************/
public static void main(String[] args) {
BinaryTreeUpsideDown.Solution tester = new BinaryTreeUpsideDown.Solution();
}
}
刚开始这个题目的意思有点看不懂, 直接甩过来两张图, 然后对于具体的flip的思路没有给出任何的说明; 最后只好仔细读题目的意思, 每一句话都尝试在给的例子当中找到体现, 最后还是大概理解了这个题目的意思; 这种题意不明确的题目你以后真实的面试的时候还是有可能碰到的, 而且面试官如果懒得跟你啰嗦, 到时候碰到这种抓瞎的情况也不是不可能的, 所以在这种没有rules, 只有例子的时候, 自己还是要稍微想到总结heuristic的思路;
本来其实也是一个很不抱希望的题目, 最后居然时间限制之内AC了, 而且是最优解: 0ms (46%);
具体的思路其实非常类似reverse linked list, 但是有一些不同的复杂性, 比如这里左右的处理, 可能会比较绕人, 这个时候就要配合题目给的这个例子来处理, 来计算怎么处理每一个变量; 之类另外一个技巧是这个gift; 我本来是指望在当前root的位置, 就直接将root.right塞下去给当前的root.left.left, 但是这样下一步到了root.left之后, 原来的root.left.left就丢失了; 所以我这里的做法就是先把这个root.right用gift来buffer起来, 等到我们实际上到了下一个level的root.left的时候, 我们就可以很从容的先把root.left.left给buffer起来, 然后用gift来顶替他;
这里另外一个小技巧是, root.right其实不需要判断是否是Null; gift是上一个level的root.right, 如果不是Null, 那么这个level肯定直接作为当前root的left就行了; 但是如果是Null又怎样呢? 如果上一个root的right是Null, 我们当前level还是要把当前root的left设置成Null, 所以根本就不需要区分处理;
discussion最优解, iterative版本跟我的几乎一样的:
@yfcheng said in Java recursive (O(logn) space) and iterative solutions (O(1) space) with explanation and figure:
This is not a very intuitive problem for me, I have to spent quite a while drawing figures to understand it. As shown in the figure, 1 shows the original tree, you can think about it as a comb, with 1, 2, 4 form the bone, and 3, 5 as the teeth. All we need to do is flip the teeth direction as shown in figure 2. We will remove the link 1--3, 2--5, and add link 2--3, and 4--5. And node 4 will be the new root.
As the recursive solution, we will keep recurse on the left child and once we are are done, we found the newRoot, which is 4 for this case. At this point, we will need to set the new children for node 2, basically the new left node is 3, and right node is 1. Here is the recursive solution:
![enter image description here][1]
Recursive:
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;
}
For the iterative solution, it follows the same thought, the only thing we need to pay attention to is to save the node information that will be overwritten.
![iterative][2]
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;
}
这个题目的recursion解法则看上去不是那么好理解, 其实recursion写法, 关键还是理解好一个root level recursion的思考方法就可以了, 也就是怎么用subsolution来组合得到大的solution; 怎样思考这个呢? 很简单, 你就按照题目给的例子, 先思考你如果call(2), 得到的是什么, 这个就是1.left得到的subsolution, 然后思考怎么用这个subsolution来组合得到大的solution, 或者说用OCaml的观点, what to do in THIS level? 尤其这里还是一个LinkedList的结构, 完全就可以用what to do with the header这样的思路来思考;
其他基本没有更好的解法了, 这个题目误打误撞直接就最优解了;
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.
For example:
Given a binary tree {1,2,3,4,5},
1
/ \
2 3
/ \
4 5
return the root of the binary tree [4,5,2,#,#,3,1].
4
/ \
5 2
/ \
3 1
confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.
OJ's Binary Tree Serialization:
The serialization of a binary tree follows a level order traversal, where '#' signifies a path terminator where no node exists below.
Here's an example:
1
/ \
2 3
/
4
\
5
The above binary tree is serialized as "{1,2,3,#,#,4,#,#,5}".
Difficulty:Medium
Total Accepted:26.9K
Total Submissions:60.5K
Contributor: LeetCode
Companies
linkedin
Related Topics
tree
Similar Questions
Reverse Linked List