# 156 Binary Tree Upside Down

## 156. Binary Tree Upside Down

## 1. Question

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
```

## 2. Implementation

**(1) Recursion**

```java
class Solution {
    public TreeNode upsideDownBinaryTree(TreeNode root) {
        if (root == null || root.left == null) {
            return root;
        }

        TreeNode newRoot = upsideDownBinaryTree(root.left);
        root.left.left = root.right;
        root.left.right = root;
        root.left = null;
        root.right = null;
        return newRoot;
    }
}
```

**(2) Iteration**

```java
class Solution {
    public TreeNode upsideDownBinaryTree(TreeNode root) {
        TreeNode curNode = root, preNode = null, nextNode = null, tempNode = null;

        while (curNode != null) {
            nextNode = curNode.left;

            curNode.left = tempNode;
            tempNode = curNode.right;
            curNode.right = preNode;
            preNode = curNode;
            curNode = nextNode;
        }
        return preNode;
    }
}
```

## 3. Time & Space Complexity

Recursion: 时间复杂度O(h), 空间复杂度O(h)

Iteration: 时间复杂度O(h), 空间复杂度O(1)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://protegejj.gitbook.io/algorithm-practice/leetcode/tree/156-binary-tree-upside-down.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.