# 156. 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.

**Example:**

```
Input: [1,2,3,4,5]

    1
   / \
  2   3
 / \
4   5

Output: return the root of the binary tree [4,5,2,#,#,3,1]

   4
  / \
 5   2
    / \
   3   1  
```

**Clarification:**

Confused what `[4,5,2,#,#,3,1]` means? Read more below on how binary tree is serialized on OJ.

The serialization of a binary tree follows a level order traversal, where '#' signifies a path terminator where no node exists below.

Here's an example:

```
   1
  / \
 2   3
    /
   4
    \
     5
```

The above binary tree is serialized as `[1,2,3,#,#,4,#,#,5]`.

{% hint style="info" %}
這題有點像是每個root, left child, right child順時針旋轉。
{% endhint %}

```cpp
// Recursion Method
TreeNode* upsideDownBinaryTree(TreeNode* root) { // time: O(n); space: O(n)
    if (!root || !root->left) return root;
    TreeNode *l = root->left, *r = root->right;
    TreeNode *newRoot = upsideDownBinaryTree(l);
    l->left = r; // original right node becomes left node
    l->right = root; // original root becomes right node
    root->left = nullptr;
    root->right = nullptr;
    return newRoot;
}
```

{% hint style="info" %}
next: 當前這輪的left node是下一輪的current node\
pre: 當前這輪的current node是下一輪的right node\
tmp: 當前這輪的right node是下一輪的left node
{% endhint %}

```cpp
// Iteration Method
TreeNode* upsideDownBinaryTree(TreeNode* root) { // time: O(n); space: O(1)
    TreeNode *cur = root, *next = nullptr, *pre = nullptr, *tmp = nullptr;
    while (cur) {
        next = cur->left; // the next iteration cur node
        cur->left = tmp;
        tmp = cur->right; // current right node is left node in the next iteration
        cur->right = pre;
        pre = cur; // cur root node is the right node in the next iteration
        cur = next;
    }
    return pre;
}
```


---

# 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://jimmylin1991.gitbook.io/practice-of-algorithm-problems/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.