Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

156. Binary Tree Upside Down

Time: $O(n)$

Space: $O(h)$

			


class Solution {
 public:
  TreeNode* upsideDownBinaryTree(TreeNode* root) {
    if (root == nullptr || root->left == nullptr)
      return root;

    TreeNode* newRoot = upsideDownBinaryTree(root->left);
    root->left->left = root->right;  // 2's left = 3 (root's right)
    root->left->right = root;        // 2's right = 1 (root)
    root->left = nullptr;
    root->right = nullptr;
    return newRoot;
  }
};




			


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; // 2's left = 3 (root's right)
    root.left.right = root;      // 2's right = 1 (root)
    root.left = null;
    root.right = null;
    return newRoot;
  }
}




			


class Solution:
  def upsideDownBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
    if not root or not root.left:
      return root

    newRoot = self.upsideDownBinaryTree(root.left)
    root.left.left = root.right  # 2's left = 3 (root's right)
    root.left.right = root  # 2's right = 1 (root)
    root.left = None
    root.right = None
    return newRoot