樹的模式模板 — 完整指南

# Python - Recursive
def preorder_traversal(root):
    result = []

    def preorder(node):
        if not node:
            return

        # Process root first
        result.append(node.val)

        # Then left subtree
        preorder(node.left)

        # Then right subtree
        preorder(node.right)

    preorder(root)
    return result

# Python - Iterative
def preorder_iterative(root):
    if not root:
        return []

    result = []
    stack = [root]

    while stack:
        node = stack.pop()
        result.append(node.val)

        # Add right first (LIFO - will process left first)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)

    return result

// Java - Recursive
public void preorderTraversal(TreeNode root, List<Integer> result) {
    if (root == null) return;

    result.add(root.val);              // Process root
    preorderTraversal(root.left, result);   // Left subtree
    preorderTraversal(root.right, result);  // Right subtree
}

// Java - Iterative
public List<Integer> preorderIterative(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) return result;

    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);

    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        result.add(node.val);

        if (node.right != null) stack.push(node.right);
        if (node.left != null) stack.push(node.left);
    }

    return result;
}

# Python - Recursive
def inorder_traversal(root):
    result = []

    def inorder(node):
        if not node:
            return

        # Left subtree first
        inorder(node.left)

        # Process root
        result.append(node.val)

        # Right subtree
        inorder(node.right)

    inorder(root)
    return result

# Python - Iterative
def inorder_iterative(root):
    result = []
    stack = []
    current = root

    while stack or current:
        # Go to leftmost node
        while current:
            stack.append(current)
            current = current.left

        # Process current node
        current = stack.pop()
        result.append(current.val)

        # Move to right subtree
        current = current.right

    return result

// Java - Recursive
public void inorderTraversal(TreeNode root, List<Integer> result) {
    if (root == null) return;

    inorderTraversal(root.left, result);    // Left subtree
    result.add(root.val);                   // Current node
    inorderTraversal(root.right, result);   // Right subtree
}

// Java - Iterative
public List<Integer> inorderIterative(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    TreeNode current = root;

    while (!stack.isEmpty() || current != null) {
        while (current != null) {
            stack.push(current);
            current = current.left;
        }

        current = stack.pop();
        result.add(current.val);
        current = current.right;
    }

    return result;
}

# Python - Recursive
def postorder_traversal(root):
    result = []

    def postorder(node):
        if not node:
            return

        # Left subtree first
        postorder(node.left)

        # Right subtree
        postorder(node.right)

        # Process root last
        result.append(node.val)

    postorder(root)
    return result

# Python - Iterative (Two Stacks)
def postorder_iterative(root):
    if not root:
        return []

    stack1 = [root]
    stack2 = []

    # Collect nodes in reverse postorder
    while stack1:
        node = stack1.pop()
        stack2.append(node)

        if node.left:
            stack1.append(node.left)
        if node.right:
            stack1.append(node.right)

    # Pop from stack2 to get postorder
    result = []
    while stack2:
        result.append(stack2.pop().val)

    return result

// Java - Recursive
public void postorderTraversal(TreeNode root, List<Integer> result) {
    if (root == null) return;

    postorderTraversal(root.left, result);   // Left subtree
    postorderTraversal(root.right, result);  // Right subtree
    result.add(root.val);                    // Current node
}

# Python - BFS with Level Grouping
from collections import deque

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

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

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

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

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

        result.append(current_level)

    return result

# Python - Simple BFS (Flat List)
def level_order_simple(root):
    if not root:
        return []

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

    while queue:
        node = queue.popleft()
        result.append(node.val)

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

    return result

// Java - BFS with Level Grouping
public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) return result;

    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);

    while (!queue.isEmpty()) {
        int levelSize = queue.size();
        List<Integer> currentLevel = new ArrayList<>();

        for (int i = 0; i < levelSize; i++) {
            TreeNode node = queue.poll();
            currentLevel.add(node.val);

            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }

        result.add(currentLevel);
    }

    return result;
}

# Python - Zigzag Level Order
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)
        current_level = deque()

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

            # Add to level based on direction
            if left_to_right:
                current_level.append(node.val)
            else:
                current_level.appendleft(node.val)

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

        result.append(list(current_level))
        left_to_right = not left_to_right

    return result

// Java - Zigzag Level Order
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) return result;

    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    boolean leftToRight = true;

    while (!queue.isEmpty()) {
        int levelSize = queue.size();
        LinkedList<Integer> currentLevel = new LinkedList<>();

        for (int i = 0; i < levelSize; i++) {
            TreeNode node = queue.poll();

            if (leftToRight) {
                currentLevel.addLast(node.val);
            } else {
                currentLevel.addFirst(node.val);
            }

            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }

        result.add(currentLevel);
        leftToRight = !leftToRight;
    }

    return result;
}

# Python - Height Calculation
def max_depth(root):
    if not root:
        return 0

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

    return 1 + max(left_height, right_height)

// Java - Height Calculation
public int maxDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }

    int leftHeight = maxDepth(root.left);
    int rightHeight = maxDepth(root.right);

    return 1 + Math.max(leftHeight, rightHeight);
}

# Python - Minimum Depth
from collections import deque

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

    queue = deque([(root, 1)])

    while queue:
        node, depth = queue.popleft()

        # Found first leaf - return immediately
        if not node.left and not node.right:
            return depth

        if node.left:
            queue.append((node.left, depth + 1))
        if node.right:
            queue.append((node.right, depth + 1))

    return 0

// Java - Minimum Depth
public int minDepth(TreeNode root) {
    if (root == null) return 0;

    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    int depth = 1;

    while (!queue.isEmpty()) {
        int levelSize = queue.size();

        for (int i = 0; i < levelSize; i++) {
            TreeNode node = queue.poll();

            if (node.left == null && node.right == null) {
                return depth;
            }

            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }

        depth++;
    }

    return depth;
}

# Python - Balanced Tree Check
def is_balanced(root):
    def check_height(node):
        if not node:
            return 0

        left_height = check_height(node.left)
        if left_height == -1:
            return -1

        right_height = check_height(node.right)
        if right_height == -1:
            return -1

        # Check balance condition
        if abs(left_height - right_height) > 1:
            return -1

        return 1 + max(left_height, right_height)

    return check_height(root) != -1

// Java - Balanced Tree Check
public boolean isBalanced(TreeNode root) {
    return checkHeight(root) != -1;
}

private int checkHeight(TreeNode node) {
    if (node == null) {
        return 0;
    }

    int leftHeight = checkHeight(node.left);
    if (leftHeight == -1) return -1;

    int rightHeight = checkHeight(node.right);
    if (rightHeight == -1) return -1;

    if (Math.abs(leftHeight - rightHeight) > 1) {
        return -1;
    }

    return 1 + Math.max(leftHeight, rightHeight);
}

# Python - Symmetric Tree
def is_symmetric(root):
    def is_mirror(left, right):
        if not left and not right:
            return True
        if not left or not right:
            return False

        return (left.val == right.val and
                is_mirror(left.left, right.right) and
                is_mirror(left.right, right.left))

    if not root:
        return True
    return is_mirror(root.left, root.right)

// Java - Symmetric Tree
public boolean isSymmetric(TreeNode root) {
    if (root == null) return true;
    return isMirror(root.left, root.right);
}

private boolean isMirror(TreeNode left, TreeNode right) {
    if (left == null && right == null) return true;
    if (left == null || right == null) return false;

    return left.val == right.val &&
           isMirror(left.left, right.right) &&
           isMirror(left.right, right.left);
}

# Python - Same Tree
def is_same_tree(p, q):
    if not p and not q:
        return True
    if not p or not q:
        return False

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

// Java - Same Tree
public boolean isSameTree(TreeNode p, TreeNode q) {
    if (p == null && q == null) return true;
    if (p == null || q == null) return false;

    return p.val == q.val &&
           isSameTree(p.left, q.left) &&
           isSameTree(p.right, q.right);
}

# Python - Minimum Depth DFS
def min_depth(root):
    if not root:
        return 0

    # If one child is missing, only consider the other
    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))

// Java - Minimum Depth DFS
public int minDepth(TreeNode root) {
    if (root == null) return 0;

    if (root.left == null) {
        return 1 + minDepth(root.right);
    }
    if (root.right == null) {
        return 1 + minDepth(root.left);
    }

    return 1 + Math.min(minDepth(root.left), minDepth(root.right));
}

# Python - Find Bottom Left Tree Value
from collections import deque

def find_bottom_left_value(root):
    queue = deque([root])
    leftmost = root.val

    while queue:
        level_size = len(queue)

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

            # First node of level
            if i == 0:
                leftmost = node.val

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

    return leftmost

// Java - Find Bottom Left Tree Value
public int findBottomLeftValue(TreeNode root) {
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    int leftmost = root.val;

    while (!queue.isEmpty()) {
        int levelSize = queue.size();

        for (int i = 0; i < levelSize; i++) {
            TreeNode node = queue.poll();

            if (i == 0) {
                leftmost = node.val;
            }

            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
    }

    return leftmost;
}

# Python - Binary Tree Maximum Path Sum
def max_path_sum(root):
    max_sum = float('-inf')

    def max_gain(node):
        nonlocal max_sum

        if not node:
            return 0

        # Max sum on left and right (ignore negative)
        left_gain = max(max_gain(node.left), 0)
        right_gain = max(max_gain(node.right), 0)

        # Update global max with path through current node
        current_path_sum = node.val + left_gain + right_gain
        max_sum = max(max_sum, current_path_sum)

        # Return max gain if continue from this node
        return node.val + max(left_gain, right_gain)

    max_gain(root)
    return max_sum

// Java - Binary Tree Maximum Path Sum
private int maxSum = Integer.MIN_VALUE;

public int maxPathSum(TreeNode root) {
    maxGain(root);
    return maxSum;
}

private int maxGain(TreeNode node) {
    if (node == null) return 0;

    int leftGain = Math.max(maxGain(node.left), 0);
    int rightGain = Math.max(maxGain(node.right), 0);

    int currentPathSum = node.val + leftGain + rightGain;
    maxSum = Math.max(maxSum, currentPathSum);

    return node.val + Math.max(leftGain, rightGain);
}

# Python - Path Sum
def has_path_sum(root, target_sum):
    if not root:
        return False

    # Leaf node - check if sum matches
    if not root.left and not root.right:
        return root.val == target_sum

    # Recurse with updated target
    remaining = target_sum - root.val
    return (has_path_sum(root.left, remaining) or
            has_path_sum(root.right, remaining))

// Java - Path Sum
public boolean hasPathSum(TreeNode root, int targetSum) {
    if (root == null) {
        return false;
    }

    if (root.left == null && root.right == null) {
        return root.val == targetSum;
    }

    int remaining = targetSum - root.val;
    return hasPathSum(root.left, remaining) ||
           hasPathSum(root.right, remaining);
}

# Python - Path Sum II
def path_sum(root, target_sum):
    result = []

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

        path.append(node.val)

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

        dfs(node.left, remaining - node.val, path)
        dfs(node.right, remaining - node.val, path)

        path.pop()  # Backtrack

    dfs(root, target_sum, [])
    return result

// Java - Path Sum II
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    dfs(root, targetSum, path, result);
    return result;
}

private void dfs(TreeNode node, int remaining, List<Integer> path,
                 List<List<Integer>> result) {
    if (node == null) return;

    path.add(node.val);

    if (node.left == null && node.right == null && remaining == node.val) {
        result.add(new ArrayList<>(path));
    }

    dfs(node.left, remaining - node.val, path, result);
    dfs(node.right, remaining - node.val, path, result);

    path.remove(path.size() - 1);  // Backtrack
}

# Python - Path Sum III
def path_sum(root, target_sum):
    def dfs(node, current_sum):
        if not node:
            return 0

        current_sum += node.val

        # Count paths ending at current node
        count = prefix_sum.get(current_sum - target_sum, 0)

        # Add current sum to map
        prefix_sum[current_sum] = prefix_sum.get(current_sum, 0) + 1

        # Recurse to children
        count += dfs(node.left, current_sum)
        count += dfs(node.right, current_sum)

        # Backtrack
        prefix_sum[current_sum] -= 1

        return count

    prefix_sum = {0: 1}
    return dfs(root, 0)

// Java - Path Sum III
private int count = 0;

public int pathSum(TreeNode root, int targetSum) {
    Map<Long, Integer> prefixSum = new HashMap<>();
    prefixSum.put(0L, 1);
    dfs(root, 0L, targetSum, prefixSum);
    return count;
}

private void dfs(TreeNode node, long currentSum, int targetSum,
                 Map<Long, Integer> prefixSum) {
    if (node == null) return;

    currentSum += node.val;

    count += prefixSum.getOrDefault(currentSum - targetSum, 0);

    prefixSum.put(currentSum, prefixSum.getOrDefault(currentSum, 0) + 1);

    dfs(node.left, currentSum, targetSum, prefixSum);
    dfs(node.right, currentSum, targetSum, prefixSum);

    prefixSum.put(currentSum, prefixSum.get(currentSum) - 1);
}

# Python - Sum Root to Leaf Numbers
def sum_numbers(root):
    def dfs(node, current_number):
        if not node:
            return 0

        current_number = current_number * 10 + node.val

        # Leaf node - return the number
        if not node.left and not node.right:
            return current_number

        # Sum from both subtrees
        return dfs(node.left, current_number) + dfs(node.right, current_number)

    return dfs(root, 0)

// Java - Sum Root to Leaf Numbers
public int sumNumbers(TreeNode root) {
    return dfs(root, 0);
}

private int dfs(TreeNode node, int currentNumber) {
    if (node == null) return 0;

    currentNumber = currentNumber * 10 + node.val;

    if (node.left == null && node.right == null) {
        return currentNumber;
    }

    return dfs(node.left, currentNumber) + dfs(node.right, currentNumber);
}

# Python - Count Good Nodes
def good_nodes(root):
    def dfs(node, max_so_far):
        if not node:
            return 0

        count = 1 if node.val >= max_so_far else 0

        new_max = max(max_so_far, node.val)
        count += dfs(node.left, new_max)
        count += dfs(node.right, new_max)

        return count

    return dfs(root, float('-inf'))

// Java - Count Good Nodes
public int goodNodes(TreeNode root) {
    return dfs(root, Integer.MIN_VALUE);
}

private int dfs(TreeNode node, int maxSoFar) {
    if (node == null) return 0;

    int count = node.val >= maxSoFar ? 1 : 0;

    int newMax = Math.max(maxSoFar, node.val);
    count += dfs(node.left, newMax);
    count += dfs(node.right, newMax);

    return count;
}

# Python - Diameter of Binary Tree
def diameter_of_binary_tree(root):
    diameter = 0

    def depth(node):
        nonlocal diameter

        if not node:
            return 0

        left_depth = depth(node.left)
        right_depth = depth(node.right)

        # Update diameter
        diameter = max(diameter, left_depth + right_depth)

        return 1 + max(left_depth, right_depth)

    depth(root)
    return diameter

// Java - Diameter of Binary Tree
private int diameter = 0;

public int diameterOfBinaryTree(TreeNode root) {
    depth(root);
    return diameter;
}

private int depth(TreeNode node) {
    if (node == null) return 0;

    int leftDepth = depth(node.left);
    int rightDepth = depth(node.right);

    diameter = Math.max(diameter, leftDepth + rightDepth);

    return 1 + Math.max(leftDepth, rightDepth);
}

# Python - Longest Univalue Path
def longest_univalue_path(root):
    longest = 0

    def dfs(node):
        nonlocal longest

        if not node:
            return 0

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

        left_path = left_length + 1 if node.left and node.left.val == node.val else 0
        right_path = right_length + 1 if node.right and node.right.val == node.val else 0

        longest = max(longest, left_path + right_path)

        return max(left_path, right_path)

    dfs(root)
    return longest

// Java - Longest Univalue Path
private int longest = 0;

public int longestUnivaluePath(TreeNode root) {
    dfs(root);
    return longest;
}

private int dfs(TreeNode node) {
    if (node == null) return 0;

    int leftLength = dfs(node.left);
    int rightLength = dfs(node.right);

    int leftPath = 0, rightPath = 0;

    if (node.left != null && node.left.val == node.val) {
        leftPath = leftLength + 1;
    }
    if (node.right != null && node.right.val == node.val) {
        rightPath = rightLength + 1;
    }

    longest = Math.max(longest, leftPath + rightPath);

    return Math.max(leftPath, rightPath);
}

# Python - Invert Binary Tree
def invert_tree(root):
    if not root:
        return None

    # Swap children
    root.left, root.right = root.right, root.left

    # Recursively invert subtrees
    invert_tree(root.left)
    invert_tree(root.right)

    return root

// Java - Invert Binary Tree
public TreeNode invertTree(TreeNode root) {
    if (root == null) return null;

    // Cache children
    TreeNode left = invertTree(root.left);
    TreeNode right = invertTree(root.right);

    // Swap
    root.left = right;
    root.right = left;

    return root;
}

# Python - Flatten Binary Tree to Linked List
def flatten(root):
    if not root:
        return

    flatten(root.left)
    flatten(root.right)

    # Save right subtree
    right = root.right

    # Move left subtree to right
    root.right = root.left
    root.left = None

    # Attach original right subtree to end
    current = root
    while current.right:
        current = current.right
    current.right = right

// Java - Flatten Binary Tree to Linked List
public void flatten(TreeNode root) {
    if (root == null) return;

    flatten(root.left);
    flatten(root.right);

    TreeNode right = root.right;

    root.right = root.left;
    root.left = null;

    TreeNode current = root;
    while (current.right != null) {
        current = current.right;
    }
    current.right = right;
}

# Python - Merge Two Binary Trees
def merge_trees(t1, t2):
    if not t1 and not t2:
        return None
    if not t1:
        return t2
    if not t2:
        return t1

    # Merge current nodes
    merged = TreeNode(t1.val + t2.val)

    # Recursively merge children
    merged.left = merge_trees(t1.left, t2.left)
    merged.right = merge_trees(t1.right, t2.right)

    return merged

// Java - Merge Two Binary Trees
public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
    if (t1 == null && t2 == null) return null;
    if (t1 == null) return t2;
    if (t2 == null) return t1;

    TreeNode merged = new TreeNode(t1.val + t2.val);

    merged.left = mergeTrees(t1.left, t2.left);
    merged.right = mergeTrees(t1.right, t2.right);

    return merged;
}

// java
// LC 117 - Populating Next Right Pointers in Each Node II
// IDEA: walk the current level through its own `next` chain; build the next level
//       onto a dummy head so missing children need no special cases
// time = O(N), space = O(1)
public Node connect(Node root) {
    Node curr = root;
    while (curr != null) {
        Node dummy = new Node(0);   // sentinel head of the level below
        Node tail  = dummy;
        for (Node node = curr; node != null; node = node.next) {
            if (node.left  != null) { tail.next = node.left;  tail = tail.next; }
            if (node.right != null) { tail.next = node.right; tail = tail.next; }
        }
        curr = dummy.next;          // descend to the level we just linked
    }
    return root;
}

# python
# LC 117 - Populating Next Right Pointers in Each Node II
# IDEA: current level is already a linked list via `next`;
#       append its children to a dummy-headed list, then descend
# time = O(N), space = O(1)
def connect(root):
    curr = root
    while curr:
        dummy = Node(0)          # sentinel head of the level below
        tail = dummy
        node = curr
        while node:
            if node.left:
                tail.next = node.left
                tail = tail.next
            if node.right:
                tail.next = node.right
                tail = tail.next
            node = node.next
        curr = dummy.next        # descend to the level we just linked
    return root

// java
// LC 116 - Populating Next Right Pointers in Each Node (perfect tree)
// IDEA: perfect tree ⇒ children always exist ⇒ link them directly from the parent level
// time = O(N), space = O(1)
public Node connect(Node root) {
    Node leftmost = root;
    while (leftmost != null && leftmost.left != null) {
        for (Node node = leftmost; node != null; node = node.next) {
            node.left.next = node.right;                       // same parent
            if (node.next != null) node.right.next = node.next.left;  // across parents
        }
        leftmost = leftmost.left;
    }
    return root;
}

# python
# LC 116 - Populating Next Right Pointers in Each Node (perfect tree)
# time = O(N), space = O(1)
def connect(root):
    leftmost = root
    while leftmost and leftmost.left:
        node = leftmost
        while node:
            node.left.next = node.right
            if node.next:
                node.right.next = node.next.left
            node = node.next
        leftmost = leftmost.left
    return root

level 1:  1                      dummy -> 2 -> 3
level 2:  2 -> 3                 dummy -> 4 -> 5 -> 7   (3 has no left child; dummy skips the hole)
level 3:  4 -> 5 -> 7            dummy -> null  -> stop

// java
// LC 337 - House Robber III
// IDEA: post-order tree DP — each node returns {best if robbed, best if skipped}
// time = O(N), space = O(H)
public int rob(TreeNode root) {
    int[] res = dfs(root);
    return Math.max(res[0], res[1]);
}

// returns {maxIfRobCurrent, maxIfSkipCurrent}
private int[] dfs(TreeNode node) {
    if (node == null) return new int[]{0, 0};

    int[] l = dfs(node.left);
    int[] r = dfs(node.right);

    int rob  = node.val + l[1] + r[1];                          // children MUST be skipped
    int skip = Math.max(l[0], l[1]) + Math.max(r[0], r[1]);     // children are free to choose

    return new int[]{rob, skip};
}

# python
# LC 337 - House Robber III
# IDEA: post-order tree DP — return (rob_this, skip_this) per node
# time = O(N), space = O(H)
def rob(root):
    def dfs(node):
        if not node:
            return (0, 0)

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

        rob_this  = node.val + l[1] + r[1]   # children must be skipped
        skip_this = max(l) + max(r)          # children choose freely

        return (rob_this, skip_this)

    return max(dfs(root))

// java
// LC 987 - Vertical Order Traversal of a Binary Tree
// IDEA: DFS collecting (col, row, val) triples, then sort col → row → val
// time = O(N log N), space = O(N)
public List<List<Integer>> verticalTraversal(TreeNode root) {
    List<int[]> nodes = new ArrayList<>();   // {col, row, val}
    dfs(root, 0, 0, nodes);

    nodes.sort((a, b) -> a[0] != b[0] ? Integer.compare(a[0], b[0])
                       : a[1] != b[1] ? Integer.compare(a[1], b[1])
                       : Integer.compare(a[2], b[2]));

    List<List<Integer>> res = new ArrayList<>();
    Integer prevCol = null;
    for (int[] n : nodes) {
        if (prevCol == null || n[0] != prevCol) {
            res.add(new ArrayList<>());
            prevCol = n[0];
        }
        res.get(res.size() - 1).add(n[2]);
    }
    return res;
}

private void dfs(TreeNode node, int row, int col, List<int[]> nodes) {
    if (node == null) return;
    nodes.add(new int[]{col, row, node.val});
    dfs(node.left,  row + 1, col - 1, nodes);
    dfs(node.right, row + 1, col + 1, nodes);
}

# python
# LC 987 - Vertical Order Traversal of a Binary Tree
# IDEA: DFS collecting (col, row, val); plain tuple sort gives col → row → val
# time = O(N log N), space = O(N)
def vertical_traversal(root):
    nodes = []

    def dfs(node, row, col):
        if not node:
            return
        nodes.append((col, row, node.val))
        dfs(node.left,  row + 1, col - 1)
        dfs(node.right, row + 1, col + 1)

    dfs(root, 0, 0)
    nodes.sort()

    res, prev_col = [], None
    for col, row, val in nodes:
        if col != prev_col:
            res.append([])
            prev_col = col
        res[-1].append(val)
    return res

// java
// LC 222 - Count Complete Tree Nodes
// IDEA: perfect subtree ⇒ 2^d - 1 in O(log n); otherwise recurse on both children
// time = O(log^2 N), space = O(log N)
public int countNodes(TreeNode root) {
    if (root == null) return 0;

    int ld = leftDepth(root), rd = rightDepth(root);
    if (ld == rd) return (1 << ld) - 1;   // perfect subtree — no traversal needed

    return 1 + countNodes(root.left) + countNodes(root.right);
}

private int leftDepth(TreeNode n)  { int d = 0; while (n != null) { d++; n = n.left;  } return d; }
private int rightDepth(TreeNode n) { int d = 0; while (n != null) { d++; n = n.right; } return d; }

# python
# LC 222 - Count Complete Tree Nodes
# IDEA: leftmost depth == rightmost depth ⇒ perfect subtree ⇒ 2^d - 1
# time = O(log^2 N), space = O(log N)
def count_nodes(root):
    if not root:
        return 0

    ld, node = 0, root
    while node:
        ld += 1
        node = node.left

    rd, node = 0, root
    while node:
        rd += 1
        node = node.right

    if ld == rd:
        return (1 << ld) - 1          # perfect subtree

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

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

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

// LC 98 - Validate Binary Search Tree
// IDEA: DFS with min/max bounds — value must be in (lo, hi)
// time = O(N), space = O(H)
public boolean isValidBST(TreeNode root) {
    return validate(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
private boolean validate(TreeNode node, long lo, long hi) {
    if (node == null) return true;
    if (node.val <= lo || node.val >= hi) return false;
    return validate(node.left, lo, node.val) && validate(node.right, node.val, hi);
}

// LC 199 - Binary Tree Right Side View
// IDEA: BFS — collect rightmost (last) node value per level
// time = O(N), space = O(N)
public List<Integer> rightSideView(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    if (root == null) return res;
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);
    while (!q.isEmpty()) {
        int size = q.size();
        for (int i = 0; i < size; i++) {
            TreeNode node = q.poll();
            if (i == size - 1) res.add(node.val);
            if (node.left  != null) q.offer(node.left);
            if (node.right != null) q.offer(node.right);
        }
    }
    return res;
}