Leetcode Tree - lydia-hsu-1111/prep GitHub Wiki
def recursive_function(node):
# Base case
if node is None:
return base_case_value
# Recursive calls
left_result = recursive_function(node.left)
right_result = recursive_function(node.right)
# Early exit condition (optional)
if some_condition_based_on(left_result, right_result):
return special_value_or_flag
# Combine left, right and current node's value for result
result = combine(left_result, right_result, node.val)
return result
Why post-order tree recursion is often trickier:
-
You need info from both children before deciding what to do at the current node. This means you have to manage and combine multiple results — sometimes carefully handling nulls, edge cases, or multiple return values.
-
It’s “bottom-up” reasoning: Unlike pre-order (root first) or in-order (mostly BSTs with sorted traversal), post-order forces you to think about solving smaller subproblems fully before you can solve the bigger one.
-
State aggregation and passing values upward: Many advanced tree problems (max path sum, diameter, subtree computations, LCA variants) require you to compute partial results for subtrees and combine them correctly. The combination logic can get subtle.
-
You have to keep track of global state (e.g., max path length) separately because the answer might not be purely from one recursive call but from combining both subtrees at the current node.
Tips to master post-order tree problems:
- Draw the tree and label return values from left and right subtrees.
- Clearly identify what your recursive function returns at each node.
- Keep a global variable outside recursion for things like max values.
- Write base cases first (null nodes).
- Practice breaking down problems into “solve left subtree”, “solve right subtree”, “combine results” pattern.
Examples to compare:
- Check Balanced Tree
class Solution:
def isBalanced(self, root: Optional[TreeNode]) -> bool:
def check(node):
if not node:
return 0
left = check(node.left)
if left is False:
return False
right = check(node.right)
if right is False:
return False
if abs(left - right) > 1:
return False
return max(left, right) + 1
return check(root) is not False
- Lowest Common Ancestor
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
def dfs(node):
if not node or node == p or node == q:
return node
left = dfs(node.left)
right = dfs(node.right)
if left and right:
return node
if left:
return left
if right:
return right
return None # optional, for clarity
return dfs(root)