Monday, November 17, 2014

[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。

5 comments:

  1. 觉得这题就是后序变成层序.

    ReplyDelete
    Replies
    1. 我也写了一个. 每次只返回根. 但是在递归前记录要链接的节点. 在自己电脑上运行了一下,没发现什么问题. 大侠们确认一下?

      TreeNode* upDown(TreeNode*root){
      if (!root) return nullptr;
      if (!root->left) return root;

      assert(root->left);
      TreeNode* l= root->left;
      TreeNode* r= root->right;
      TreeNode* newH= upDown(root->left);
      l->right= root;
      l->left= upDown(r);
      root->left=0;
      root->right=0;
      if (r) { r->left=0; r->right=0;}
      return newH;
      }

      Delete
  2. 不是很理解题目。。这样子满足题目的条件吗?
    1
    / \
    3 2
    / \
    5 4

    ReplyDelete