LeetCode Patterns ·

🎯 Binary Tree Patterns

1️⃣ Core Framework

When discussing Binary Tree Patterns, I frame it as:

What binary tree problems are
Tree traversal patterns
Top-down recursion
Bottom-up recursion
Path problems
Subtree problems
BST-specific problems
Level-order BFS problems
Global answer patterns
Senior-level explanation

2️⃣ What Problem Are We Solving?

Binary tree problems ask us to process a tree where each node has at most two children.

They are commonly used for:

Tree traversal
Maximum depth
Minimum depth
Balanced binary tree
Diameter of binary tree
Path sum
Lowest common ancestor
Validate binary search tree
Kth smallest in BST
Serialize and deserialize tree
Invert binary tree
Same tree
Symmetric tree
Subtree of another tree
Maximum path sum
Level order traversal

The core idea is:

A binary tree problem is usually solved by deciding:
what each node needs from its parent,
what each node needs from its children,
and what each node should return.

👉 Interview Answer

Binary tree problems are usually recursion problems.

The key is to decide whether the problem is top-down, bottom-up, path-based, subtree-based, BST-based, or level-order.

Once I know what each node should return, the recursive structure becomes much clearer.

3️⃣ Basic Binary Tree Structure

Tree Node

Most interview problems use:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

Example Tree

Key Properties

A binary tree node has:

value
left child
right child

A node can have:

children -> leaf node
child
children

👉 Interview Answer

A binary tree is a tree where each node has at most two children.

Most recursive solutions treat the left subtree and right subtree as smaller versions of the same problem.

That is why binary tree problems often fit naturally into recursion.

4️⃣ Core Recursive Template

Basic Shape

def dfs(node):
    if not node:
        return base_value

    left = dfs(node.left)
    right = dfs(node.right)

    return combine(left, right, node)

What to Decide

For each binary tree problem, ask:

What should null return?
What does left subtree return?
What does right subtree return?
How does current node combine them?
Does the answer need a global variable?

👉 Interview Answer

My default binary tree template is DFS recursion.

I define a base case for null nodes, recursively solve the left and right subtrees, then combine their results at the current node.

The main challenge is defining what each recursive call returns.

5️⃣ Top-Down Recursion

Meaning

Top-down recursion passes information from parent to child.

Examples:

current path sum
current depth
current min/max bound
current path list

Template

def dfs(node, state_from_parent):
    if not node:
        return

    new_state = update(state_from_parent, node)

    dfs(node.left, new_state)
    dfs(node.right, new_state)

Common Problems

Path Sum
Path Sum II
Validate BST with bounds
Root-to-leaf paths
Maximum depth with depth parameter

👉 Interview Answer

Top-down recursion passes state from the parent to the children.

It is useful when the current node needs information from its ancestors, such as path sum, current depth, or valid value bounds.

The recursive call carries updated state downward.

6️⃣ Bottom-Up Recursion

Meaning

Bottom-up recursion collects information from children first.

Examples:

height
diameter
balanced status
max path contribution
subtree size
subtree sum

Template

def dfs(node):
    if not node:
        return base_value

    left = dfs(node.left)
    right = dfs(node.right)

    return combine(left, right, node)

Common Problems

Maximum Depth
Balanced Binary Tree
Diameter of Binary Tree
Maximum Path Sum
Count Nodes
LCA

👉 Interview Answer

Bottom-up recursion is used when a node’s answer depends on information from its children.

The recursive function first gets results from the left and right subtrees, then computes and returns the result for the current subtree.

Many height, diameter, and subtree problems use this pattern.

7️⃣ Preorder, Inorder, Postorder

Preorder

Root -> Left -> Right

Use when:

parent before children
serialization
copy tree
top-down path state

Inorder

Left -> Root -> Right

Use when:

BST sorted order
kth smallest
validate BST

Postorder

Left -> Right -> Root

Use when:

children before parent
height
diameter
balanced tree
subtree aggregation

👉 Interview Answer

Preorder processes the current node before children.

Inorder processes left, current, then right, and is especially important for BSTs because it gives sorted order.

Postorder processes children before the current node, which is useful when the parent needs child results.

8️⃣ Maximum Depth

Problem

Find the maximum depth of a binary tree.

Bottom-Up Idea

The depth of a node is:

1 + max(left depth, right depth)

Code

def max_depth(root):
    if not root:
        return 0

    left = max_depth(root.left)
    right = max_depth(root.right)

    return 1 + max(left, right)

👉 Interview Answer

Maximum Depth is a bottom-up recursion problem.

I compute the depth of the left and right subtrees, then return one plus the larger depth.

Null nodes return zero.

9️⃣ Minimum Depth

Problem

Find the minimum depth from root to a leaf.

Important Edge Case

A missing child does not count as a leaf path.

Wrong:

1 + min(left_depth, right_depth)

This fails when one child is null.

Code

def min_depth(root):
    if not root:
        return 0

    if not root.left:
        return 1 + min_depth(root.right)

    if not root.right:
        return 1 + min_depth(root.left)

    return 1 + min(min_depth(root.left), min_depth(root.right))

👉 Interview Answer

Minimum Depth is similar to maximum depth, but missing children need special handling.

A null child is not a valid path to a leaf.

If one child is missing, I must take the depth of the other child.

🔟 Balanced Binary Tree

Problem

Determine whether the tree is height-balanced.

A tree is balanced if:

for every node,
left and right subtree heights differ by at most 1

Bottom-Up Idea

Return:

height if balanced
-1 if unbalanced

Code

def is_balanced(root):
    def height(node):
        if not node:
            return 0

        left = height(node.left)
        if left == -1:
            return -1

        right = height(node.right)
        if right == -1:
            return -1

        if abs(left - right) > 1:
            return -1

        return 1 + max(left, right)

    return height(root) != -1

👉 Interview Answer

Balanced Binary Tree is a bottom-up problem.

Each node needs the height of both subtrees before deciding whether it is balanced.

I return -1 as a failure signal if any subtree is unbalanced, otherwise I return the subtree height.

1️⃣1️⃣ Diameter of Binary Tree

Problem

Find the longest path between any two nodes.

The path may or may not pass through the root.

Key Insight

At each node, the longest path passing through that node is:

left_height + right_height

Code

def diameter_of_binary_tree(root):
    answer = 0

    def height(node):
        nonlocal answer

        if not node:
            return 0

        left = height(node.left)
        right = height(node.right)

        answer = max(answer, left + right)

        return 1 + max(left, right)

    height(root)
    return answer

👉 Interview Answer

Diameter is a bottom-up recursion problem.

At each node, I compute the left and right heights.

The path through the current node has length left height plus right height.

I update a global answer while returning subtree height upward.

1️⃣2️⃣ Maximum Path Sum

Problem

Find the maximum path sum in a binary tree.

A path can start and end at any nodes, but it must be connected.

Key Insight

For each node, there are two concepts:

path passing through current node as answer candidate
path contribution returned to parent

The path through current node can use both sides:

node.val + left_gain + right_gain

But contribution to parent can only use one side:

node.val + max(left_gain, right_gain)

Code

def max_path_sum(root):
    answer = float("-inf")

    def gain(node):
        nonlocal answer

        if not node:
            return 0

        left_gain = max(gain(node.left), 0)
        right_gain = max(gain(node.right), 0)

        current_path = node.val + left_gain + right_gain
        answer = max(answer, current_path)

        return node.val + max(left_gain, right_gain)

    gain(root)
    return answer

👉 Interview Answer

Maximum Path Sum is a postorder problem with a global answer.

At each node, I compute the best gain from the left and right children.

A path using the current node as the highest point can take both sides, but the value returned to the parent can only take one side.

Negative gains are ignored by taking max with zero.

1️⃣3️⃣ Path Sum

Problem

Determine whether there is a root-to-leaf path whose sum equals target.

Top-Down Idea

Pass remaining sum downward.

At leaf:

remaining == node.val

Code

def has_path_sum(root, target_sum):
    if not root:
        return False

    if not root.left and not root.right:
        return target_sum == root.val

    remaining = target_sum - root.val

    return (
        has_path_sum(root.left, remaining)
        or
        has_path_sum(root.right, remaining)
    )

👉 Interview Answer

Path Sum is a top-down DFS problem.

I pass the remaining target sum down the tree.

When I reach a leaf, I check whether the leaf value equals the remaining target.

1️⃣4️⃣ Path Sum II

Problem

Return all root-to-leaf paths whose sum equals target.

Backtracking Pattern

Maintain:

current path
remaining sum

At leaf, if sum matches, append a copy of path.

Code

def path_sum(root, target_sum):
    result = []
    path = []

    def dfs(node, remaining):
        if not node:
            return

        path.append(node.val)

        if not node.left and not node.right and remaining == node.val:
            result.append(path[:])
        else:
            dfs(node.left, remaining - node.val)
            dfs(node.right, remaining - node.val)

        path.pop()

    dfs(root, target_sum)
    return result

👉 Interview Answer

Path Sum II uses DFS with backtracking.

I keep a current path while going down the tree.

If I reach a leaf and the sum matches, I append a copy of the path.

Then I pop the current node before returning.

1️⃣5️⃣ Binary Tree Paths

Problem

Return all root-to-leaf paths.

Example:

["1->2->5", "1->3"]

Code

def binary_tree_paths(root):
    result = []

    def dfs(node, path):
        if not node:
            return

        path.append(str(node.val))

        if not node.left and not node.right:
            result.append("->".join(path))
        else:
            dfs(node.left, path)
            dfs(node.right, path)

        path.pop()

    dfs(root, [])
    return result

👉 Interview Answer

Binary Tree Paths is a top-down path problem.

I maintain the current path from root to node.

When I reach a leaf, I convert the path into a string and add it to the result.

Then I backtrack before returning to the parent.

1️⃣6️⃣ Lowest Common Ancestor

Problem

Find the lowest node that has both p and q as descendants.

Postorder Idea

If current node is p or q:
    return current node

Search left and right.

If both sides return non-null:
    current node is LCA

Otherwise:
    return the non-null side

Code

def lowest_common_ancestor(root, p, q):
    if not root or root == p or root == q:
        return root

    left = lowest_common_ancestor(root.left, p, q)
    right = lowest_common_ancestor(root.right, p, q)

    if left and right:
        return root

    return left if left else right

👉 Interview Answer

LCA in a binary tree is a postorder recursion problem.

If both left and right subtrees return non-null, the current node is where p and q split, so it is the LCA.

If only one side returns non-null, I pass that result upward.

1️⃣7️⃣ Same Tree

Problem

Determine whether two binary trees are identical.

Code

def is_same_tree(p, q):
    if not p and not q:
        return True

    if not p or not q:
        return False

    if p.val != q.val:
        return False

    return (
        is_same_tree(p.left, q.left)
        and
        is_same_tree(p.right, q.right)
    )

👉 Interview Answer

To check whether two trees are the same, I compare the current nodes first.

If both are null, they match.

If only one is null or their values differ, they do not match.

Then I recursively compare left subtrees and right subtrees.

1️⃣8️⃣ Symmetric Tree

Problem

Determine whether a tree is symmetric around its center.

Mirror Logic

Two subtrees are mirrors if:

left.val == right.val
left.left mirrors right.right
left.right mirrors right.left

Code

def is_symmetric(root):
    def mirror(left, right):
        if not left and not right:
            return True

        if not left or not right:
            return False

        if left.val != right.val:
            return False

        return (
            mirror(left.left, right.right)
            and
            mirror(left.right, right.left)
        )

    return mirror(root.left, root.right) if root else True

👉 Interview Answer

Symmetric Tree compares two subtrees as mirrors.

The left subtree’s left child must match the right subtree’s right child, and the left subtree’s right child must match the right subtree’s left child.

This is a recursive two-tree comparison problem.

1️⃣9️⃣ Invert Binary Tree

Problem

Swap the left and right child of every node.

Code

def invert_tree(root):
    if not root:
        return None

    root.left, root.right = invert_tree(root.right), invert_tree(root.left)

    return root

👉 Interview Answer

Invert Binary Tree is a recursive subtree transformation problem.

For each node, I recursively invert the left and right subtrees, then swap them.

The base case is a null node.

2️⃣0️⃣ Subtree of Another Tree

Problem

Determine whether subRoot is a subtree of root.

Idea

At each node in root, check whether the tree starting there is the same as subRoot.

Code

def is_subtree(root, sub_root):
    def same(a, b):
        if not a and not b:
            return True

        if not a or not b:
            return False

        if a.val != b.val:
            return False

        return same(a.left, b.left) and same(a.right, b.right)

    if not root:
        return False

    if same(root, sub_root):
        return True

    return is_subtree(root.left, sub_root) or is_subtree(root.right, sub_root)

👉 Interview Answer

Subtree of Another Tree combines traversal and tree comparison.

I traverse every node in the main tree.

At each node, I check whether the subtree rooted there is identical to subRoot.

If any match is found, I return true.

2️⃣1️⃣ Validate Binary Search Tree

BST Rule

For every node:

left subtree values < node.val
right subtree values > node.val

But this rule must apply with ancestor bounds, not only direct children.

Bounds Code

def is_valid_bst(root):
    def validate(node, low, high):
        if not node:
            return True

        if not (low < node.val < high):
            return False

        return (
            validate(node.left, low, node.val)
            and
            validate(node.right, node.val, high)
        )

    return validate(root, float("-inf"), float("inf"))

Inorder Alternative

def is_valid_bst(root):
    previous = None

    def inorder(node):
        nonlocal previous

        if not node:
            return True

        if not inorder(node.left):
            return False

        if previous is not None and node.val <= previous:
            return False

        previous = node.val

        return inorder(node.right)

    return inorder(root)

👉 Interview Answer

Validate BST can be solved with bounds recursion or inorder traversal.

Bounds recursion passes the valid value range from ancestors to children.

Inorder works because a valid BST should produce a strictly increasing sequence.

2️⃣2️⃣ Kth Smallest in BST

Key Insight

Inorder traversal of a BST gives sorted order.

So kth smallest is the kth visited node.

Code

def kth_smallest(root, k):
    stack = []
    current = root

    while current or stack:
        while current:
            stack.append(current)
            current = current.left

        current = stack.pop()
        k -= 1

        if k == 0:
            return current.val

        current = current.right

👉 Interview Answer

In a BST, inorder traversal visits nodes in increasing order.

Therefore, the kth smallest value is the kth value visited during inorder traversal.

The iterative version can stop as soon as k reaches zero.

2️⃣3️⃣ Level Order Traversal

Problem

Return nodes level by level.

BFS Code

from collections import deque

def level_order(root):
    if not root:
        return []

    result = []
    queue = deque([root])

    while queue:
        level_size = len(queue)
        level = []

        for _ in range(level_size):
            node = queue.popleft()
            level.append(node.val)

            if node.left:
                queue.append(node.left)

            if node.right:
                queue.append(node.right)

        result.append(level)

    return result

👉 Interview Answer

Level Order Traversal is BFS on a tree.

I use a queue.

For each level, I process exactly the current queue size, then push children for the next level.

This keeps nodes grouped by depth.

2️⃣4️⃣ Right Side View

Problem

Return the nodes visible from the right side.

BFS Idea

For each level, the last node is visible.

Code

from collections import deque

def right_side_view(root):
    if not root:
        return []

    result = []
    queue = deque([root])

    while queue:
        level_size = len(queue)

        for i in range(level_size):
            node = queue.popleft()

            if i == level_size - 1:
                result.append(node.val)

            if node.left:
                queue.append(node.left)

            if node.right:
                queue.append(node.right)

    return result

👉 Interview Answer

Right Side View can be solved with level order traversal.

At each level, the last node processed is the node visible from the right side.

So I add the last node of every level to the result.

2️⃣5️⃣ Zigzag Level Order

Problem

Return level order traversal, but alternate direction on each level.

Code

from collections import deque

def zigzag_level_order(root):
    if not root:
        return []

    result = []
    queue = deque([root])
    left_to_right = True

    while queue:
        level_size = len(queue)
        level = []

        for _ in range(level_size):
            node = queue.popleft()
            level.append(node.val)

            if node.left:
                queue.append(node.left)

            if node.right:
                queue.append(node.right)

        if not left_to_right:
            level.reverse()

        result.append(level)
        left_to_right = not left_to_right

    return result

👉 Interview Answer

Zigzag Level Order is a BFS level traversal with alternating output order.

I process each level normally, then reverse the level result every other level.

The traversal stays the same; only the output order changes.

2️⃣6️⃣ Serialize and Deserialize Binary Tree

Problem

Convert a tree to a string and back.

Preorder With Null Markers

Null markers are necessary to preserve structure.

Code

def serialize(root):
    result = []

    def dfs(node):
        if not node:
            result.append("#")
            return

        result.append(str(node.val))
        dfs(node.left)
        dfs(node.right)

    dfs(root)
    return ",".join(result)


def deserialize(data):
    values = iter(data.split(","))

    def dfs():
        value = next(values)

        if value == "#":
            return None

        node = TreeNode(int(value))
        node.left = dfs()
        node.right = dfs()

        return node

    return dfs()

👉 Interview Answer

Serialize and Deserialize can be solved with preorder traversal and null markers.

Preorder records the root before children.

Null markers preserve missing child positions, which makes reconstruction unambiguous.

2️⃣7️⃣ Construct Tree From Preorder and Inorder

Problem

Given preorder and inorder traversal arrays, construct the binary tree.

Key Idea

Preorder gives root.

Inorder gives left and right subtree boundaries.

Code

def build_tree(preorder, inorder):
    index_map = {}

    for i, value in enumerate(inorder):
        index_map[value] = i

    preorder_index = 0

    def build(left, right):
        nonlocal preorder_index

        if left > right:
            return None

        root_val = preorder[preorder_index]
        preorder_index += 1

        root = TreeNode(root_val)

        mid = index_map[root_val]

        root.left = build(left, mid - 1)
        root.right = build(mid + 1, right)

        return root

    return build(0, len(inorder) - 1)

👉 Interview Answer

Preorder tells me the root of the current subtree.

Inorder tells me which values belong to the left and right subtrees.

I use a hashmap to find the root position in inorder quickly, then recursively build both sides.

2️⃣8️⃣ Count Complete Tree Nodes

Problem

Count nodes in a complete binary tree.

Complete Tree Optimization

If left height equals right height, the subtree is perfect.

Node count is:

2^height - 1

Code

def count_nodes(root):
    def left_height(node):
        height = 0

        while node:
            height += 1
            node = node.left

        return height

    def right_height(node):
        height = 0

        while node:
            height += 1
            node = node.right

        return height

    if not root:
        return 0

    lh = left_height(root)
    rh = right_height(root)

    if lh == rh:
        return (1 << lh) - 1

    return 1 + count_nodes(root.left) + count_nodes(root.right)

👉 Interview Answer

For a complete binary tree, if the leftmost height equals the rightmost height, the subtree is perfect.

Then the node count is 2^height - 1.

Otherwise, I recursively count the left and right subtrees.

2️⃣9️⃣ Common Edge Cases

Empty Tree

root = None

Return depends on problem:

[]
0
False
None

Single Node

Often both root and leaf.

Skewed Tree

Depth becomes O(n).

Recursion stack can become O(n).

Negative Values

Important for maximum path sum.

Do not initialize answer to 0.

Use:

float("-inf")

Duplicate Values

Do not compare only values if node identity matters.

Null Children

Important for minimum depth, serialization, and tree construction.

👉 Interview Answer

Common binary tree edge cases include empty trees, single-node trees, skewed trees, negative values, duplicate values, and null children.

Negative values are especially important for maximum path sum, where the answer should not be initialized to zero.

3️⃣0️⃣ Common Mistakes

Mistake 1: Forgetting Null Base Case

Every recursive tree function needs:

if not node:
    return ...

Mistake 2: Confusing Top-Down and Bottom-Up

Path problems often pass state downward.

Height and diameter problems usually return information upward.

Mistake 3: Using Inorder Sorted Assumption on Non-BST

Inorder is sorted only for BST.

Mistake 4: Not Copying Path

Wrong:

result.append(path)

Correct:

result.append(path[:])

Mistake 5: Wrong Minimum Depth Logic

Null child is not a valid leaf path.

Mistake 6: Maximum Path Sum Returning Both Sides to Parent

A path returned to parent can only choose one side.

Mistake 7: Comparing Values Instead of Nodes

For LCA or subtree identity, compare node references when possible.

👉 Interview Answer

Common binary tree mistakes include forgetting the null base case, mixing up top-down and bottom-up recursion, assuming inorder is sorted for non-BSTs, not copying paths in backtracking, mishandling minimum depth, returning both sides in maximum path sum, and comparing values when node identity matters.

3️⃣1️⃣ When Binary Tree Pattern Applies

Good Fit

Use binary tree patterns when the problem asks for:

tree traversal
height or depth
root-to-leaf path
subtree information
ancestor relationship
tree comparison
BST validation
level order
serialization
tree construction

Problem Signals

Look for words like:

root
left
right
leaf
subtree
ancestor
descendant
path
height
depth
level
BST
serialize
binary tree

👉 Interview Answer

I consider binary tree patterns whenever the problem involves nodes with left and right children.

Then I identify whether the task is traversal, path tracking, subtree aggregation, BST-specific logic, or level-order processing.

That decision determines whether I use preorder, inorder, postorder, or BFS.

3️⃣2️⃣ When Binary Tree Pattern Does Not Apply

Not Good Fit

Binary tree recursion alone may not be enough when:

graph has cycles
need shortest path in weighted graph
need repeated LCA queries at scale
need dynamic tree updates
need subtree range queries

Better Alternatives

Problem Type	Better Pattern
Graph with cycles	Graph DFS with visited
Shortest path	BFS / Dijkstra
Many LCA queries	Binary Lifting
Dynamic tree path queries	Heavy-Light Decomposition
Subtree range queries	Euler Tour + Segment Tree
Dependency ordering	Topological Sort

👉 Interview Answer

Binary tree recursion works well for static tree traversal and subtree computation.

But if the structure has cycles, it becomes a graph problem and needs visited state.

If there are many repeated queries or dynamic updates, preprocessing structures like binary lifting, Euler tour, or segment tree may be needed.

3️⃣3️⃣ Standard Templates

Bottom-Up DFS Template

def dfs(node):
    if not node:
        return base_value

    left = dfs(node.left)
    right = dfs(node.right)

    return combine(left, right, node)

Top-Down DFS Template

def dfs(node, state):
    if not node:
        return

    new_state = update(state, node)

    dfs(node.left, new_state)
    dfs(node.right, new_state)

Path Backtracking Template

def dfs(node):
    if not node:
        return

    path.append(node.val)

    if not node.left and not node.right:
        process(path)
    else:
        dfs(node.left)
        dfs(node.right)

    path.pop()

Level Order BFS Template

from collections import deque

def level_order(root):
    if not root:
        return []

    queue = deque([root])
    result = []

    while queue:
        level_size = len(queue)
        level = []

        for _ in range(level_size):
            node = queue.popleft()
            level.append(node.val)

            if node.left:
                queue.append(node.left)

            if node.right:
                queue.append(node.right)

        result.append(level)

    return result

BST Bounds Template

def validate(node, low, high):
    if not node:
        return True

    if not (low < node.val < high):
        return False

    return (
        validate(node.left, low, node.val)
        and
        validate(node.right, node.val, high)
    )

Global Answer Template

answer = initial_value

def dfs(node):
    nonlocal answer

    if not node:
        return base_value

    left = dfs(node.left)
    right = dfs(node.right)

    answer = max(answer, candidate(node, left, right))

    return value_to_parent(node, left, right)

🧠 Staff-Level Answer Final

👉 Interview Answer Full Version

Binary tree problems are usually about recursively processing a node, its left subtree, and its right subtree.

The most important step is to identify the problem pattern.

If the problem passes information from parent to child, it is top-down recursion. Examples include path sum, root-to-leaf path tracking, and BST validation with bounds.

If the problem needs child results before the parent can decide, it is bottom-up recursion. Examples include maximum depth, balanced binary tree, diameter, maximum path sum, and LCA.

Traversal order matters. Preorder processes the parent before children, so it is useful for serialization and top-down state. Inorder is important for BST problems because it gives sorted order. Postorder processes children before parent, which is useful for height, diameter, and subtree aggregation. Level order uses BFS and is useful for level-based output, right side view, zigzag traversal, and minimum depth.

For path problems, I usually use DFS with backtracking. I maintain a current path, process it at leaf nodes, and pop before returning.

For subtree aggregation problems, I define what each recursive call returns. For example, maximum depth returns height. Balanced tree returns height or -1. Diameter returns height while updating a global answer. Maximum path sum returns one-side gain while updating a global maximum.

For BST problems, I use either inorder traversal or value bounds. I also avoid assuming inorder is sorted unless the tree is actually a BST.

For comparison problems like Same Tree, Symmetric Tree, and Subtree of Another Tree, I compare structure and values recursively.

At a senior level, I would explain: whether the problem is top-down or bottom-up, what each recursive call returns, whether a global answer is needed, whether the problem is BST-specific, whether level-order BFS is required, and how edge cases like empty trees, skewed trees, duplicate values, and negative values are handled.

⭐ Final Insight

Binary Tree Patterns 的核心不是“看到 tree 就递归”。

它的核心是先判断是哪一种 tree pattern：

top-down state passing， bottom-up subtree aggregation， path backtracking， BST inorder/bounds， level-order BFS， tree comparison， global-answer recursion。

Senior-level 的重点是：

null node 返回什么，当前 node 从 parent 拿什么，当前 node 从 children 拿什么， recursive function 返回什么，是否需要 global answer，是否是 BST，是否要按 level 处理， negative values 和 skewed tree 怎么处理。

能讲清楚这些， Binary Tree Patterns 就是一类处理 subtree information、path information、ancestor relationship、BST order 和 level structure 的核心模式。

中文部分

🎯 Binary Tree Patterns

1️⃣ 核心框架

讨论 Binary Tree Patterns 时，我通常从：

Binary tree problems 是什么
Tree traversal patterns
Top-down recursion
Bottom-up recursion
Path problems
Subtree problems
BST-specific problems
Level-order BFS problems
Global answer patterns
高级工程师解释方式

2️⃣ 要解决什么问题？

Binary tree problems 处理的是每个 node 最多有两个 children 的 tree。

它常用于：

Tree traversal
Maximum depth
Minimum depth
Balanced binary tree
Diameter of binary tree
Path sum
Lowest common ancestor
Validate binary search tree
Kth smallest in BST
Serialize and deserialize tree
Invert binary tree
Same tree
Symmetric tree
Subtree of another tree
Maximum path sum
Level order traversal

核心思想是：

Binary tree problem 通常要先判断：
每个 node 需要从 parent 得到什么，
每个 node 需要从 children 得到什么，
以及每个 node 应该返回什么。

👉 面试回答

Binary tree problems 通常是 recursion problems。

关键是判断题目属于 top-down、 bottom-up、 path-based、 subtree-based、 BST-based，还是 level-order。

一旦定义清楚每个 node 应该返回什么， recursive structure 就会清晰很多。

3️⃣ Basic Binary Tree Structure

Tree Node

大多数面试题使用：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

Example Tree

Key Properties

一个 binary tree node 有：

value
left child
right child

一个 node 可以有：

children -> leaf node
child
children

👉 面试回答

Binary tree 是每个 node 最多有两个 children 的 tree。

大多数 recursive solutions 都把 left subtree 和 right subtree 看成相同问题的更小版本。

所以 binary tree problems 很自然适合 recursion。

4️⃣ Core Recursive Template

Basic Shape

def dfs(node):
    if not node:
        return base_value

    left = dfs(node.left)
    right = dfs(node.right)

    return combine(left, right, node)

What to Decide

每道 binary tree problem 都要问：

Null node 应该返回什么？
Left subtree 返回什么？
Right subtree 返回什么？
Current node 如何 combine？
是否需要 global variable？

👉 面试回答

我的默认 binary tree 模板是 DFS recursion。

先定义 null node 的 base case，然后递归处理 left 和 right subtrees，最后在 current node 合并结果。

最大的关键是定义每个 recursive call 返回什么。

5️⃣ Top-Down Recursion

Meaning

Top-down recursion 把信息从 parent 传给 child。

Examples:

current path sum
current depth
current min/max bound
current path list

Template

def dfs(node, state_from_parent):
    if not node:
        return

    new_state = update(state_from_parent, node)

    dfs(node.left, new_state)
    dfs(node.right, new_state)

Common Problems

Path Sum
Path Sum II
Validate BST with bounds
Root-to-leaf paths
Maximum depth with depth parameter

👉 面试回答

Top-down recursion 会把 state 从 parent 传到 children。

当 current node 需要 ancestor information 时，这种模式很有用。

例如 path sum、current depth、或 valid value bounds。

Recursive call 会把更新后的 state 继续向下传递。

6️⃣ Bottom-Up Recursion

Meaning

Bottom-up recursion 先从 children 收集信息。

Examples:

height
diameter
balanced status
max path contribution
subtree size
subtree sum

Template

def dfs(node):
    if not node:
        return base_value

    left = dfs(node.left)
    right = dfs(node.right)

    return combine(left, right, node)

Common Problems

Maximum Depth
Balanced Binary Tree
Diameter of Binary Tree
Maximum Path Sum
Count Nodes
LCA

👉 面试回答

Bottom-up recursion 适合 current node 的答案依赖 children 信息的场景。

Recursive function 会先拿到 left 和 right subtree 的结果，再计算当前 subtree 的结果并返回给 parent。

很多 height、diameter 和 subtree problems 都是这个模式。

7️⃣ Preorder, Inorder, Postorder

Preorder

Root -> Left -> Right

适合：

parent before children
serialization
copy tree
top-down path state

Inorder

Left -> Root -> Right

适合：

BST sorted order
kth smallest
validate BST

Postorder

Left -> Right -> Root

适合：

children before parent
height
diameter
balanced tree
subtree aggregation

👉 面试回答

Preorder 在 children 前处理 current node。

Inorder 是 left、current、right，对 BST 特别重要，因为它会得到 sorted order。

Postorder 在 current node 前先处理 children，适合 parent 需要 child results 的问题。

8️⃣ Maximum Depth

Problem

求 binary tree 的 maximum depth。

Bottom-Up Idea

一个 node 的 depth 是：

1 + max(left depth, right depth)

Code

def max_depth(root):
    if not root:
        return 0

    left = max_depth(root.left)
    right = max_depth(root.right)

    return 1 + max(left, right)

👉 面试回答

Maximum Depth 是 bottom-up recursion problem。

我先计算 left 和 right subtrees 的 depth，然后返回两者较大值加一。

Null node 返回 0。

9️⃣ Minimum Depth

Problem

求 root 到 leaf 的 minimum depth。

Important Edge Case

Missing child 不能算作 leaf path。

错误写法：

1 + min(left_depth, right_depth)

当一个 child 是 null 时会出错。

Code

def min_depth(root):
    if not root:
        return 0

    if not root.left:
        return 1 + min_depth(root.right)

    if not root.right:
        return 1 + min_depth(root.left)

    return 1 + min(min_depth(root.left), min_depth(root.right))

👉 面试回答

Minimum Depth 和 maximum depth 类似，但是 missing children 要特别处理。

Null child 不是一条 valid leaf path。

如果一个 child 缺失，必须选择另一个 child 的 depth。

🔟 Balanced Binary Tree

Problem

判断 tree 是否 height-balanced。

Balanced 表示：

对每个 node，
left 和 right subtree heights 的差不超过 1

Bottom-Up Idea

height if balanced
-1 if unbalanced

Code

def is_balanced(root):
    def height(node):
        if not node:
            return 0

        left = height(node.left)
        if left == -1:
            return -1

        right = height(node.right)
        if right == -1:
            return -1

        if abs(left - right) > 1:
            return -1

        return 1 + max(left, right)

    return height(root) != -1

👉 面试回答

Balanced Binary Tree 是 bottom-up problem。

每个 node 需要先知道两个 subtrees 的 height，才能判断自己是否 balanced。

如果任何 subtree 已经 unbalanced，我返回 -1 作为 failure signal。

否则返回当前 subtree 的 height。

1️⃣1️⃣ Diameter of Binary Tree

Problem

求任意两个 nodes 之间的最长 path。

这个 path 不一定经过 root。

Key Insight

对每个 node，经过该 node 的最长 path 是：

left_height + right_height

Code

def diameter_of_binary_tree(root):
    answer = 0

    def height(node):
        nonlocal answer

        if not node:
            return 0

        left = height(node.left)
        right = height(node.right)

        answer = max(answer, left + right)

        return 1 + max(left, right)

    height(root)
    return answer

👉 面试回答

Diameter 是 bottom-up recursion problem。

在每个 node，我计算 left height 和 right height。

经过 current node 的 path 长度是 left height 加 right height。

我一边返回 subtree height，一边更新 global answer。

1️⃣2️⃣ Maximum Path Sum

Problem

求 binary tree 中的 maximum path sum。

Path 可以从任意 node 开始，到任意 node 结束，但必须是 connected path。

Key Insight

对每个 node，有两个概念：

以 current node 为拐点的 answer candidate
返回给 parent 的 path contribution

经过 current node 的 path 可以使用两边：

node.val + left_gain + right_gain

但返回给 parent 的 contribution 只能选择一边：

node.val + max(left_gain, right_gain)

Code

def max_path_sum(root):
    answer = float("-inf")

    def gain(node):
        nonlocal answer

        if not node:
            return 0

        left_gain = max(gain(node.left), 0)
        right_gain = max(gain(node.right), 0)

        current_path = node.val + left_gain + right_gain
        answer = max(answer, current_path)

        return node.val + max(left_gain, right_gain)

    gain(root)
    return answer

👉 面试回答

Maximum Path Sum 是 postorder problem，并且需要 global answer。

对每个 node，我计算来自 left 和 right child 的 best gain。

以 current node 为最高点的 path 可以取左右两边。

但返回给 parent 的 path 只能选择一边，因为 path 不能分叉。

对 negative gain，我用 max with zero 忽略它。

1️⃣3️⃣ Path Sum

Problem

判断是否存在 root-to-leaf path，其 sum 等于 target。

Top-Down Idea

把 remaining sum 往下传。

到 leaf 时检查：

remaining == node.val

Code

def has_path_sum(root, target_sum):
    if not root:
        return False

    if not root.left and not root.right:
        return target_sum == root.val

    remaining = target_sum - root.val

    return (
        has_path_sum(root.left, remaining)
        or
        has_path_sum(root.right, remaining)
    )

👉 面试回答

Path Sum 是 top-down DFS problem。

我把剩余 target sum 传到 children。

当到达 leaf 时，检查 leaf value 是否等于 remaining target。

1️⃣4️⃣ Path Sum II

Problem

返回所有 sum 等于 target 的 root-to-leaf paths。

Backtracking Pattern

维护：

current path
remaining sum

到 leaf 时，如果 sum match，就 append path copy。

Code

def path_sum(root, target_sum):
    result = []
    path = []

    def dfs(node, remaining):
        if not node:
            return

        path.append(node.val)

        if not node.left and not node.right and remaining == node.val:
            result.append(path[:])
        else:
            dfs(node.left, remaining - node.val)
            dfs(node.right, remaining - node.val)

        path.pop()

    dfs(root, target_sum)
    return result

👉 面试回答

Path Sum II 使用 DFS with backtracking。

我维护 current path。

如果到达 leaf 且 sum match，就把 path 的 copy 加入 result。

然后在返回前 pop current node。

1️⃣5️⃣ Binary Tree Paths

Problem

返回所有 root-to-leaf paths。

Example:

["1->2->5", "1->3"]

Code

def binary_tree_paths(root):
    result = []

    def dfs(node, path):
        if not node:
            return

        path.append(str(node.val))

        if not node.left and not node.right:
            result.append("->".join(path))
        else:
            dfs(node.left, path)
            dfs(node.right, path)

        path.pop()

    dfs(root, [])
    return result

👉 面试回答

Binary Tree Paths 是 top-down path problem。

我维护从 root 到 current node 的 path。

当到达 leaf 时，把 path 转成 string 加入 result。

返回 parent 前要 backtrack。

1️⃣6️⃣ Lowest Common Ancestor

Problem

找到同时拥有 p 和 q 作为 descendants 的最低 node。

Postorder Idea

如果 current node 是 p 或 q:
    return current node

搜索 left 和 right。

如果两边都返回 non-null:
    current node 是 LCA

否则:
    返回 non-null 那一边

Code

def lowest_common_ancestor(root, p, q):
    if not root or root == p or root == q:
        return root

    left = lowest_common_ancestor(root.left, p, q)
    right = lowest_common_ancestor(root.right, p, q)

    if left and right:
        return root

    return left if left else right

👉 面试回答

Binary tree 中的 LCA 是 postorder recursion problem。

如果 left 和 right subtrees 都返回 non-null，说明当前 node 是 p 和 q 的 split point，所以它是 LCA。

如果只有一边返回 non-null，就把那一边的结果向上传递。

1️⃣7️⃣ Same Tree

Problem

判断两棵 binary trees 是否完全相同。

Code

def is_same_tree(p, q):
    if not p and not q:
        return True

    if not p or not q:
        return False

    if p.val != q.val:
        return False

    return (
        is_same_tree(p.left, q.left)
        and
        is_same_tree(p.right, q.right)
    )

👉 面试回答

判断两棵树是否相同，我先比较 current nodes。

如果两个都是 null，它们相同。

如果只有一个是 null，或 values 不同，它们不同。

然后递归比较 left subtrees 和 right subtrees。

1️⃣8️⃣ Symmetric Tree

Problem

判断一棵 tree 是否关于中心对称。

Mirror Logic

两个 subtrees 是 mirror 如果：

left.val == right.val
left.left mirrors right.right
left.right mirrors right.left

Code

def is_symmetric(root):
    def mirror(left, right):
        if not left and not right:
            return True

        if not left or not right:
            return False

        if left.val != right.val:
            return False

        return (
            mirror(left.left, right.right)
            and
            mirror(left.right, right.left)
        )

    return mirror(root.left, root.right) if root else True

👉 面试回答

Symmetric Tree 是两个 subtrees 的 mirror comparison。

Left subtree 的 left child 要匹配 right subtree 的 right child。

Left subtree 的 right child 要匹配 right subtree 的 left child。

这是一个 recursive two-tree comparison problem。

1️⃣9️⃣ Invert Binary Tree

Problem

交换每个 node 的 left 和 right child。

Code

def invert_tree(root):
    if not root:
        return None

    root.left, root.right = invert_tree(root.right), invert_tree(root.left)

    return root

👉 面试回答

Invert Binary Tree 是 recursive subtree transformation。

对每个 node，我递归 invert 左右 subtrees，然后交换它们。

Base case 是 null node。

2️⃣0️⃣ Subtree of Another Tree

Problem

判断 subRoot 是否是 root 的 subtree。

Idea

在 root 的每个 node 上，检查以该 node 开始的 subtree 是否和 subRoot 相同。

Code

def is_subtree(root, sub_root):
    def same(a, b):
        if not a and not b:
            return True

        if not a or not b:
            return False

        if a.val != b.val:
            return False

        return same(a.left, b.left) and same(a.right, b.right)

    if not root:
        return False

    if same(root, sub_root):
        return True

    return is_subtree(root.left, sub_root) or is_subtree(root.right, sub_root)

👉 面试回答

Subtree of Another Tree 结合了 tree traversal 和 tree comparison。

我遍历 main tree 的每个 node。

在每个 node 上，检查以它为 root 的 subtree 是否和 subRoot 完全相同。

只要找到一个 match，就返回 true。

2️⃣1️⃣ Validate Binary Search Tree

BST Rule

对每个 node：

left subtree values < node.val
right subtree values > node.val

但这个 rule 要考虑 ancestor bounds，不能只比较 direct children。

Bounds Code

def is_valid_bst(root):
    def validate(node, low, high):
        if not node:
            return True

        if not (low < node.val < high):
            return False

        return (
            validate(node.left, low, node.val)
            and
            validate(node.right, node.val, high)
        )

    return validate(root, float("-inf"), float("inf"))

Inorder Alternative

def is_valid_bst(root):
    previous = None

    def inorder(node):
        nonlocal previous

        if not node:
            return True

        if not inorder(node.left):
            return False

        if previous is not None and node.val <= previous:
            return False

        previous = node.val

        return inorder(node.right)

    return inorder(root)

👉 面试回答

Validate BST 可以用 bounds recursion 或 inorder traversal。

Bounds recursion 会把 ancestor 决定的 valid range 传给 children。

Inorder 可行，因为 valid BST 的 inorder sequence 必须严格递增。

2️⃣2️⃣ Kth Smallest in BST

Key Insight

BST 的 inorder traversal 是 sorted order。

所以 kth smallest 是 inorder 访问到的第 k 个 node。

Code

def kth_smallest(root, k):
    stack = []
    current = root

    while current or stack:
        while current:
            stack.append(current)
            current = current.left

        current = stack.pop()
        k -= 1

        if k == 0:
            return current.val

        current = current.right

👉 面试回答

在 BST 中， inorder traversal 会按 increasing order 访问 nodes。

因此 kth smallest value 就是 inorder traversal 中第 k 个访问到的 value。

Iterative version 可以在 k 变成 0 时提前停止。

2️⃣3️⃣ Level Order Traversal

Problem

按 level 返回 nodes。

BFS Code

from collections import deque

def level_order(root):
    if not root:
        return []

    result = []
    queue = deque([root])

    while queue:
        level_size = len(queue)
        level = []

        for _ in range(level_size):
            node = queue.popleft()
            level.append(node.val)

            if node.left:
                queue.append(node.left)

            if node.right:
                queue.append(node.right)

        result.append(level)

    return result

👉 面试回答

Level Order Traversal 是 tree 上的 BFS。

我用 queue。

每一层先记录当前 queue size，然后处理 exactly 这一层的 nodes，并把 children 加入下一层。

这样可以按 depth grouping nodes。

2️⃣4️⃣ Right Side View

Problem

返回从右侧能看到的 nodes。

BFS Idea

每一层的最后一个 node 可见。

Code

from collections import deque

def right_side_view(root):
    if not root:
        return []

    result = []
    queue = deque([root])

    while queue:
        level_size = len(queue)

        for i in range(level_size):
            node = queue.popleft()

            if i == level_size - 1:
                result.append(node.val)

            if node.left:
                queue.append(node.left)

            if node.right:
                queue.append(node.right)

    return result

👉 面试回答

Right Side View 可以用 level order traversal。

每一层最后处理的 node，就是从右边能看到的 node。

所以我把每一层的最后一个 node 加入 result。

2️⃣5️⃣ Zigzag Level Order

Problem

返回 level order traversal，但每层方向交替。

Code

from collections import deque

def zigzag_level_order(root):
    if not root:
        return []

    result = []
    queue = deque([root])
    left_to_right = True

    while queue:
        level_size = len(queue)
        level = []

        for _ in range(level_size):
            node = queue.popleft()
            level.append(node.val)

            if node.left:
                queue.append(node.left)

            if node.right:
                queue.append(node.right)

        if not left_to_right:
            level.reverse()

        result.append(level)
        left_to_right = not left_to_right

    return result

👉 面试回答

Zigzag Level Order 是 BFS level traversal 加 alternating output order。

我正常处理每一层，然后每隔一层 reverse 当前 level 的结果。

Traversal 本身不变，只是输出顺序交替。

2️⃣6️⃣ Serialize and Deserialize Binary Tree

Problem

把 tree 转成 string，再从 string 还原 tree。

Preorder With Null Markers

Null markers 用来保留结构。

Code

def serialize(root):
    result = []

    def dfs(node):
        if not node:
            result.append("#")
            return

        result.append(str(node.val))
        dfs(node.left)
        dfs(node.right)

    dfs(root)
    return ",".join(result)


def deserialize(data):
    values = iter(data.split(","))

    def dfs():
        value = next(values)

        if value == "#":
            return None

        node = TreeNode(int(value))
        node.left = dfs()
        node.right = dfs()

        return node

    return dfs()

👉 面试回答

Serialize and Deserialize 可以用 preorder traversal 加 null markers。

Preorder 先记录 root，再记录 children。

Null markers 可以保留 missing child positions，让 reconstruction 没有歧义。

2️⃣7️⃣ Construct Tree From Preorder and Inorder

Problem

给定 preorder 和 inorder traversal arrays，构造 binary tree。

Key Idea

Preorder 给出 root。

Inorder 给出 left 和 right subtree boundaries。

Code

def build_tree(preorder, inorder):
    index_map = {}

    for i, value in enumerate(inorder):
        index_map[value] = i

    preorder_index = 0

    def build(left, right):
        nonlocal preorder_index

        if left > right:
            return None

        root_val = preorder[preorder_index]
        preorder_index += 1

        root = TreeNode(root_val)

        mid = index_map[root_val]

        root.left = build(left, mid - 1)
        root.right = build(mid + 1, right)

        return root

    return build(0, len(inorder) - 1)

👉 面试回答

Preorder 告诉我当前 subtree 的 root。

Inorder 告诉我哪些 values 属于 left subtree，哪些 values 属于 right subtree。

我用 hashmap 快速找到 root 在 inorder 中的位置，然后递归构造左右两边。

2️⃣8️⃣ Count Complete Tree Nodes

Problem

计算 complete binary tree 中的 nodes 数量。

Complete Tree Optimization

如果 left height 等于 right height，说明 subtree 是 perfect binary tree。

Node count 是：

2^height - 1

Code

def count_nodes(root):
    def left_height(node):
        height = 0

        while node:
            height += 1
            node = node.left

        return height

    def right_height(node):
        height = 0

        while node:
            height += 1
            node = node.right

        return height

    if not root:
        return 0

    lh = left_height(root)
    rh = right_height(root)

    if lh == rh:
        return (1 << lh) - 1

    return 1 + count_nodes(root.left) + count_nodes(root.right)

👉 面试回答

对 complete binary tree，如果最左 height 等于最右 height，说明当前 subtree 是 perfect tree。

这时 node count 是 2^height - 1。

否则，递归计算 left 和 right subtrees。

2️⃣9️⃣ 常见 Edge Cases

Empty Tree

root = None

返回值取决于问题：

[]
0
False
None

Single Node

通常 root 同时也是 leaf。

Skewed Tree

Depth 会变成 O(n)。

Recursion stack 也可能是 O(n)。

Negative Values

对 maximum path sum 很重要。

不要把 answer 初始化成 0。

使用：

float("-inf")

Duplicate Values

如果 node identity 重要，不要只比较 values。

Null Children

Minimum depth、serialization 和 tree construction 都需要特别处理 null children。

👉 面试回答

Binary tree 常见 edge cases 包括 empty tree、 single-node tree、 skewed tree、 negative values、 duplicate values，以及 null children。

Negative values 对 maximum path sum 特别重要，因为 answer 不应该初始化成 0。

3️⃣0️⃣ 常见错误

Mistake 1: 忘记 Null Base Case

每个 recursive tree function 都需要：

if not node:
    return ...

Mistake 2: 混淆 Top-Down 和 Bottom-Up

Path problems 通常向下传 state。

Height 和 diameter problems 通常向上返回信息。

Mistake 3: 对 Non-BST 使用 Inorder Sorted 假设

Inorder 只有在 BST 中才是 sorted。

Mistake 4: 没有 Copy Path

错误：

result.append(path)

正确：

result.append(path[:])

Mistake 5: Minimum Depth Logic 错误

Null child 不是 valid leaf path。

Mistake 6: Maximum Path Sum 把两边都返回给 Parent

返回给 parent 的 path 只能选择一边。

Mistake 7: 比较 Values 而不是 Nodes

对 LCA 或 subtree identity，尽量比较 node reference。

👉 面试回答

Binary tree 常见错误包括：忘记 null base case、混淆 top-down 和 bottom-up recursion、错误假设 non-BST 的 inorder 是 sorted、 backtracking 时没有 copy path、 minimum depth 对 null child 处理错误、 maximum path sum 中把两边都返回给 parent、以及在 node identity 重要时只比较 values。

3️⃣1️⃣ 什么时候 Binary Tree Pattern 适用？

Good Fit

当题目问：

tree traversal
height or depth
root-to-leaf path
subtree information
ancestor relationship
tree comparison
BST validation
level order
serialization
tree construction

Problem Signals

看到这些关键词想到 binary tree pattern：

root
left
right
leaf
subtree
ancestor
descendant
path
height
depth
level
BST
serialize
binary tree

👉 面试回答

当问题涉及有 left 和 right children 的 nodes 时，我会考虑 binary tree patterns。

然后判断任务是 traversal、path tracking、 subtree aggregation、BST-specific logic，还是 level-order processing。

这个判断会决定使用 preorder、inorder、postorder 还是 BFS。

3️⃣2️⃣ 什么时候 Binary Tree Pattern 不适用？

Not Good Fit

Binary tree recursion alone 不一定够：

graph has cycles
need shortest path in weighted graph
need repeated LCA queries at scale
need dynamic tree updates
need subtree range queries

Better Alternatives

Problem Type	Better Pattern
Graph with cycles	Graph DFS with visited
Shortest path	BFS / Dijkstra
Many LCA queries	Binary Lifting
Dynamic tree path queries	Heavy-Light Decomposition
Subtree range queries	Euler Tour + Segment Tree
Dependency ordering	Topological Sort

👉 面试回答

Binary tree recursion 适合 static tree traversal 和 subtree computation。

但如果结构有 cycles，就变成 graph problem，需要 visited state。

如果有大量 repeated queries 或 dynamic updates，可能需要 binary lifting、Euler tour、或 segment tree 这类 preprocessing structures。

3️⃣3️⃣ 标准模板

Bottom-Up DFS Template

def dfs(node):
    if not node:
        return base_value

    left = dfs(node.left)
    right = dfs(node.right)

    return combine(left, right, node)

Top-Down DFS Template

def dfs(node, state):
    if not node:
        return

    new_state = update(state, node)

    dfs(node.left, new_state)
    dfs(node.right, new_state)

Path Backtracking Template

def dfs(node):
    if not node:
        return

    path.append(node.val)

    if not node.left and not node.right:
        process(path)
    else:
        dfs(node.left)
        dfs(node.right)

    path.pop()

Level Order BFS Template

from collections import deque

def level_order(root):
    if not root:
        return []

    queue = deque([root])
    result = []

    while queue:
        level_size = len(queue)
        level = []

        for _ in range(level_size):
            node = queue.popleft()
            level.append(node.val)

            if node.left:
                queue.append(node.left)

            if node.right:
                queue.append(node.right)

        result.append(level)

    return result

BST Bounds Template

def validate(node, low, high):
    if not node:
        return True

    if not (low < node.val < high):
        return False

    return (
        validate(node.left, low, node.val)
        and
        validate(node.right, node.val, high)
    )

Global Answer Template

answer = initial_value

def dfs(node):
    nonlocal answer

    if not node:
        return base_value

    left = dfs(node.left)
    right = dfs(node.right)

    answer = max(answer, candidate(node, left, right))

    return value_to_parent(node, left, right)

🧠 Staff-Level Answer Final

👉 面试回答完整版本

Binary tree problems 通常是在递归处理一个 node、它的 left subtree 和 right subtree。

最重要的是先识别问题模式。

如果问题是把 information 从 parent 传到 child，它就是 top-down recursion。例如 path sum、root-to-leaf path tracking、以及 BST validation with bounds。

如果问题需要 children results 后 parent 才能决定，它就是 bottom-up recursion。例如 maximum depth、balanced binary tree、 diameter、maximum path sum 和 LCA。

Traversal order 很重要。 Preorder 先处理 parent，适合 serialization 和 top-down state。 Inorder 对 BST 重要，因为它给出 sorted order。 Postorder 先处理 children，适合 height、diameter 和 subtree aggregation。 Level order 使用 BFS，适合 level-based output、right side view、 zigzag traversal 和 minimum depth。

对 path problems，我通常使用 DFS with backtracking。维护 current path，在 leaf node 处理 path，返回前 pop。

对 subtree aggregation problems，我会定义每个 recursive call 返回什么。例如 maximum depth 返回 height。 Balanced tree 返回 height 或 -1。 Diameter 返回 height，同时更新 global answer。 Maximum path sum 返回 one-side gain，同时更新 global maximum。

对 BST problems，我使用 inorder traversal 或 value bounds。同时注意：只有 BST 的 inorder 才是 sorted，普通 binary tree 不一定。

对 comparison problems，比如 Same Tree、Symmetric Tree、和 Subtree of Another Tree，我会递归比较 structure 和 values。

高级工程师解释 binary tree patterns 时，我会讲清楚：题目是 top-down 还是 bottom-up，每个 recursive call 返回什么，是否需要 global answer，是否是 BST-specific，是否需要 level-order BFS，以及 empty tree、skewed tree、 duplicate values、negative values 这些 edge cases 如何处理。

⭐ Final Insight

Binary Tree Patterns 的核心不是“看到 tree 就递归”。

它的核心是先判断是哪一种 tree pattern：

top-down state passing， bottom-up subtree aggregation， path backtracking， BST inorder/bounds， level-order BFS， tree comparison， global-answer recursion。

Senior-level 的重点是：

null node 返回什么，当前 node 从 parent 拿什么，当前 node 从 children 拿什么， recursive function 返回什么，是否需要 global answer，是否是 BST，是否要按 level 处理， negative values 和 skewed tree 怎么处理。

能讲清楚这些， Binary Tree Patterns 就是一类处理 subtree information、path information、ancestor relationship、BST order 和 level structure 的核心模式。