NeetCode #471LC-156MediumTrees
← Back to All Problems#471 · #156 · Binary Tree Upside Down(上下翻转二叉树)
📌 Problem Statement & Constraints
Given the root of a binary tree, turn it upside down: the original leftmost path becomes the new left spine, with each original left child becoming a parent whose right child is the original parent. Return the new root. Constraints: the number of nodes is in
[0, 10]; every right node either has a sibling or no children.💡 Core Algorithmic Approaches
- Recurse all the way down the left spine; the deepest left node becomes the new root.
- On the way back up, the current node's left child becomes its parent, and the current node becomes that parent's right child.
- The original right child of the current node becomes the new left child of the promoted node.
- This is a bottom-up relinking, which the recursion's return value makes natural.
💻 Benchmark Python3 Implementation
class Solution:
def upsideDownBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
# the deepest left node becomes the new root
if not root or not root.left:
return root
new_root = self.upsideDownBinaryTree(root.left)
# promote root.left, attaching root and its old right child
root.left.left = root.right # old right child -> new left
root.left.right = root # old parent -> new right
root.left = root.right = None # the old parent becomes a leaf
return new_root⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): each node on the left spine is visited once.
💾 Space Complexity
O(h) for the recursion stack, where h is the length of the left spine.
⚠️ Interview Pitfalls & Follow-ups
- Returning
rootinstead ofnew_root: the original root ends up deep in the new tree. - Forgetting to clear
root.leftandroot.right: the old parent would keep stale children and create cycles. - Attaching
root.rightto the wrong slot: the original right child becomes the promoted node's left child. - Trying an iterative top-down approach: the relinking depends on the deepest node being known first, which the bottom-up recursion provides naturally.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.