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

这题有一个重要的限制就是，整个树的任何一个右孩子都不会再生枝节，基本就是一个梳子的形状。对于树类型的题目，首先可以想到一种递归的思路：把左子树继续颠倒，颠倒完后，原来的那个左孩子的左右孩子指针分别指向原来的根节点以及原来的右兄弟节点即可。

递归实现：

 public TreeNode upsideDownBinaryTree(TreeNode root) {
    if (root == null) {
        return null;
    }

    return upsideDownBinaryTreeHelper(root, null);
}

private TreeNode upsideDownBinaryTreeHelper(TreeNode root, TreeNode parent) {
    if (root == null) {
        return parent;
    }

    TreeNode newNode = upsideDownBinaryTreeHelper(root.left, root);

    root.left = (parent == null ? null : parent.right);
    root.right = parent;

    return newNode;
}

迭代实现

public TreeNode upsideDownBinaryTree(TreeNode root) {
    if (root == null) {
        return null;
    }

    TreeNode parent = null;
    TreeNode parentRightChild = null;
    TreeNode p = root;

    while (p != null) {
        TreeNode next = p.left;
        p.left = parentRightChild;
        parentRightChild = p.right;

        p.right = parent;

        parent = p;
        p = next;
    }

    return parent;
}

Reference

1 Invert Binary Tree – Leetcode Lintcode Java