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:
The original left child becomes the new root.
The original root becomes the new right child.
The original right child becomes the new left child.
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:

**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
/**
* 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
/**
* 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
*/
Last updated
Was this helpful?