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.
Solutions
Solution 1
PythonJavaC++Go
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def upsideDownBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if root is None or root.left is None:
return root
new_root = self.upsideDownBinaryTree(root.left)
root.left.right = root
root.left.left = root.right
root.left = None
root.right = None
return new_root(code-box)
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public TreeNode upsideDownBinaryTree(TreeNode root) {
if (root == null || root.left == null) {
return root;
}
TreeNode newRoot = upsideDownBinaryTree(root.left);
root.left.right = root;
root.left.left = root.right;
root.left = null;
root.right = null;
return newRoot;
}
}(code-box)
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* upsideDownBinaryTree(TreeNode* root) {
if (!root || !root->left) return root;
TreeNode* newRoot = upsideDownBinaryTree(root->left);
root->left->right = root;
root->left->left = root->right;
root->left = nullptr;
root->right = nullptr;
return newRoot;
}
};(code-box)
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func upsideDownBinaryTree(root *TreeNode) *TreeNode {
if root == nil || root.Left == nil {
return root
}
newRoot := upsideDownBinaryTree(root.Left)
root.Left.Right = root
root.Left.Left = root.Right
root.Left = nil
root.Right = nil
return newRoot
}(code-box)
