[LeetCode新题] Binary Tree Upside Down

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  

思路：

LeetCode最近出了收费模式的新题，需要买他们出的电子书才能做。不过既然已经免费使用了它家这么多资源，就当买本书做点贡献。

这题第一眼看上去觉得没头绪，不知道怎么上下翻转和左右翻转。但在纸上画几个例子就清楚了。以题目的例子来解释：

1. 对于一个parent来说，加入有right node，必须得有left node。而有left node，right node可以为空。而right node必须为叶子节点。所以该树每层至多有2个节点，并且2节点有共同的parent。

2. 所以对于最底层来说，必有一个left node，而这个left node则为整个新树的根 —— 例子中的4为最底层的左节点，最后成为新树的root。

3. 原树的根节点，变为了新树的最右节点。

3. 对于子树1 2 3来说，需要在以2为根的子树2 4 5建立成新树4 5 2后，插入到新树的最右节点2下面。原树的根节点root为left child，原树root->right为新树的left nnode

递归实现：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

class Solution { public: TreeNode *upsideDownBinaryTree(TreeNode *root) { TreeNode *temp, *newRoot = NULL; temp = buildUpsideDownBT(root, newRoot); return newRoot; } TreeNode *buildUpsideDownBT(TreeNode *root, TreeNode *&newRoot) { if(!root) return root; if(!root->left && !root->right) { newRoot = root; return root; } TreeNode *parent = buildUpsideDownBT(root->left, newRoot); parent->left = root->right; parent->right = root; root->left = root->right = NULL; return parent->right; } };

总结：
1. 这个递归的核心是，每次建立好一个新的子树后，要返回新子树的最右节点（ln 19)，以便上层的节点可以接回到这个节点的下面。
2. 但如果只返回最右节点，则我们无法知道最后整个新树的根在哪里。所以再base case里必须给新根赋值(ln 12)
3. 每次需要reset最右节点的left/right node，否则最后一层递归，递归到例子中的1节点时，返回前1节点的left/right node仍然为原来的值，而并不为NULL。