Leetcode

Binary Tree Upside Down

Approach 1: Recursive

  • Time:O(n)
  • Space:O(h)

C++

class Solution {
 public:
  TreeNode* upsideDownBinaryTree(TreeNode* root) {
    if (!root || !root->left)
      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;
  }
};

JAVA

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;
  }
}

Python

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

Approach 2: Iterative

  • Time:O(n)
  • Space:O(1)

C++

class Solution {
 public:
  TreeNode* upsideDownBinaryTree(TreeNode* root) {
    TreeNode* prevRoot = nullptr;
    TreeNode* prevRightChild = nullptr;

    while (root) {
      TreeNode* nextRoot = root->left;  // cache next root
      root->left = prevRightChild;
      prevRightChild = root->right;
      root->right = prevRoot;
      prevRoot = root;  // record previous root
      root = nextRoot;  // update root
    }

    return prevRoot;
  }
};

JAVA

class Solution {
  public TreeNode upsideDownBinaryTree(TreeNode root) {
    TreeNode prevRoot = null;
    TreeNode prevRightChild = null;

    while (root != null) {
      TreeNode nextRoot = root.left; // cache next root
      root.left = prevRightChild;
      prevRightChild = root.right;
      root.right = prevRoot;
      prevRoot = root; // record previous root
      root = nextRoot; // update root
    }

    return prevRoot;
  }
}

Python

class Solution:
  def upsideDownBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
    prevRoot = None
    prevRightChild = None

    while root:
      nextRoot = root.left  # cache next root
      root.left = prevRightChild
      prevRightChild = root.right
      root.right = prevRoot
      prevRoot = root  # record previous root
      root = nextRoot  # update root

    return prevRoot