1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    private TreeNode ans;

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

    private void helper(TreeNode node, TreeNode parent) {
        if (node.left != null) {
            helper(node.left, node);
        }
        ans = ans == null ? node : ans;
        if (parent != null) {
            node.right = parent;
            node.left = parent.right;
            parent.left = null;
            parent.right = null;
        }
    }
}

递归方法的话从bottom到top来去upside down, 因为如果从top到bottom先做的话, 之前tree的信息就会丢失.

这里的条件是每个right node肯定有它对应的sibling以及每个right node没有children.

时间复杂度: O(h) h是树的高度.
空间复杂度: O(h) h是树的高度.