Upside Down

Upside Down DFS.

• Time: O(n)
• Space: O(1)

public TreeNode upsideDown(TreeNode root) {
    return upsideDown(root, null);
}
private TreeNode upsideDown(TreeNode root, TreeNode parent) {
    if (root == null) return root;
    TreeNode ret = upsideDown(root.left, root);
    root.left = parent;
    root.right = parent != null ? parent.right : null;
    return ret;
}

Upside Down Recursive.

• Time: O(n)
• Space: O(1)

public TreeNode upsideDown(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    while (root != null) {
        stack.push(root);
        root = root.left;
    }
    TreeNode ret = stack.peek();
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        TreeNode next = stack.peek();
        node.right = next;
        node.left = next != null ? next.right : null;
    }
    return ret;
}