# 0156. Binary Tree Upside Down

<https://leetcode.com/problems/binary-tree-upside-down>

## Description

Given the `root` of a binary tree, turn the tree upside down and return *the new root*.

You can turn a binary tree upside down with the following steps:

1. The original left child becomes the new root.
2. The original root becomes the new right child.
3. The original right child becomes the new left child.

![](https://assets.leetcode.com/uploads/2020/08/29/main.jpg) The mentioned steps are done level by level. It is **guaranteed** that every right node has a sibling (a left node with the same parent) and has no children.

**Example 1:**

![](https://assets.leetcode.com/uploads/2020/08/29/updown.jpg)

```
**Input:** root = [1,2,3,4,5]
**Output:** [4,5,2,null,null,3,1]
```

**Example 2:**

```
**Input:** root = []
**Output:** []
```

**Example 3:**

```
**Input:** root = [1]
**Output:** [1]
```

**Constraints:**

* The number of nodes in the tree will be in the range `[0, 10]`.
* `1 <= Node.val <= 10`
* Every right node in the tree has a sibling (a left node that shares the same parent).
* Every right node in the tree has no children.

## ac

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode upsideDownBinaryTree(TreeNode root) {
        // edge cases
        if (root == null) return root;

        // get leftmost node
        TreeNode res = root;
        while (res.left != null) res = res.left;

        // recursion reverse left tree
        reverse(root);

        // return
        return res;
    }
    private void reverse(TreeNode root) {
        // exit
        if (root.left == null) return;

        // handle
        // recursion left
        reverse(root.left);

        // reverse itself
        root.left.left = root.right;
        root.left.right = root;
        root.left = null;
        root.right = null;
    }
}

// bottom up
// never touch right tree
```

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode upsideDownBinaryTree(TreeNode root) {
        // exit
        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;
    }
}

/*
no need to change right node
*/
```