Binary Tree Upside Down

• Medium
• keyword: map
• 类似: 2 sum closest

题目意思: 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)] OROROROR [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.

• 没看懂这个OROROROR是的断句是断在哪里. 看来是英文没学好: 这个or显然是: either A or B. 见我在原题目所加的中括号. 所以题目意思就是: 所有右儿子要么是空, 要么就是叶子节点而且有左兄弟.
• 也可以说: 所有右儿子都没有子树!

• 大致思路: 图解:

idea1.1: recursion bottom-up

• 很直白的解法: 其实就是discuss: explain: Binary tree representation of N-ery trees

• 翻译过来就是:

  • 递归向下的直到left-most leaf, 这个是反转后的newRoot. 然后walk-up tree, 将root.left指向root.sibling, 将root.right指向root.parent.
  • 由于root.sibling/parent只有walk-up tree的时候才能处理, 所以放在recursion call之后处理.

• 由于要在walk up的时候指向parent/sibling. 所以我在recur.param里面使用stack保存向下走的时候的right kid. 同时由于最终返回的newRoot其实是确定的, 就是left-most leaf, 所以用一个array保存它.

• 在walk up的时候, 将newRoot.left指向stack.pop, 将newRoot.right指向root. 并且返回的是newRoot的更新后的右儿子.

• 代码如下

public TreeNode upsideDownBinaryTreeSLOW(TreeNode root) {
    TreeNode[] ans = new TreeNode[1];
    TreeNode res = helper(root, new Stack<TreeNode>(), ans) ;
    return ans[0];
  }

private TreeNode helper(TreeNode root, Stack<TreeNode> stk, TreeNode[] ans) {
    if (root.left == null && root.right == null) {
        ans[0] = root;
        return root;
    }
    TreeNode upRoot = helper(root.left, stk, ans);
    upRoot.left = stk.pop();
    upRoot.right = root;
    return upRoot.right; // 注意返回值不是upRoot! 而是upRoot.right, 从而向上走并且update其指针.
}

• 结果排名垫底.

idea1.2: 还是recursion bottom-up

• 这里参考的是Leetcode discuss
• 思路类似, 但是注意到, recursion call的返回值始终指向最终newRoot. 所以方法和recursion解决LinkedList reverse一样, 参考yuanbin的gitbook.
• 代码如下

public TreeNode upsideDownBinaryTreeSLOW(TreeNode root) {
    TreeNode res = helper(root) ;
    return res;
  }

private TreeNode helper(TreeNode root) {
    if (root == null || root.left == null && root.right == null) {  // 第一个判断条件很好的解决了corner case
        return root;
    }
    TreeNode newRoot = helper(root.left);
    root.left.left = root.right;  // 处理root.left
    root.left.right = root;
    root.left = null;  // 处理root. 注意不要cyclic了
    root.right = null;
    return newRoot;  // 始终指向left-most leaf
}

idea1.3: 米群导师cpcs大作 link

• 思路和idea2类似, 但是多一个param保存parent, 这样walk-up的时候可以一直走到老root.
• 代码如下

public TreeNode upsideDownBinaryTreeSLOW(TreeNode root) {
    TreeNode res = helper(root, null) ;
    return res;
  }

private TreeNode helper(TreeNode root, TreeNode parent) {
    if (root == null) {
        return parent;
    }
    TreeNode newRoot = helper(root.left, root);
    root.left = parent == null ? parent : parent.right;  // 合并了root, root.left的update到一起.
    root.right = parent;
    return newRoot;  // 始终指向left-most leaf
}

小结

• recursion的方法很好的解决了overwrite的问题, 因为walk-down到bottom的时候才向上overwrite.
• 看看1.2和1.3方法的代码的区别, cpcs和discuss的方法类似, 但是cpcs将root和root.left的update放在了一起. 很妙.
• 其实这个题目在理解了题意之后就知道, 其实和reverse LinkedList一样, 只不过从1个pointer变成2个pointer.

idea2: iteration解决问题

• 代码如下, Leetcode discuss讲得好:

  Just think about how you can save the tree information you need before changing the tree structure.

private TreeNode iteration(TreeNode root) {
    TreeNode curr = root;
    TreeNode prev = null;
    TreeNode temp = null;
    TreeNode next = null;

    while (curr != null) {
      next = curr.left;
      curr.left = temp;
      temp = curr.right;
      curr.right = prev;

      prev = curr;
      curr = next;
    }
    return prev;
  }