樹狀資料結構 — 概念與模式

# Tree Structure
      1
     / \
    2   3
   / \  
  4   5

# Array Representation: [1, 2, 3, 4, 5]
# Index mapping:
# - Root at index 0
# - For node at index i:
#   - Left child at index 2*i + 1  
#   - Right child at index 2*i + 2
#   - Parent at index (i-1)/2

Top-Down (Pre-order)                Bottom-Up (Post-order)
─────────────────────               ──────────────────────
      1  ← start here                    1  ← combine here
     / \  pass depth=1                  / \  return heights
    2   3  depth=2                     2   3  left=1, right=1
   / \     depth=3                    / \     left=2, right=0
  4   5  → update global max        4   5  → return max+1

// LC 104 — Top-Down: pass depth down, update global max
// 3 variants: (a) void helper + global var, (b) void helper + depth param, (c) return depth param

// Variant A: void helper + global var (simplest top-down)
int maxDepth = 0;

public int maxDepth_topDown(TreeNode root) {
    dfs(root, 1);       // start at depth 1
    return maxDepth;
}

private void dfs(TreeNode root, int depth) {
    if (root == null) return;

    // Pre-order position: update answer with current state
    maxDepth = Math.max(maxDepth, depth);

    // Pass depth+1 DOWN to children
    dfs(root.left, depth + 1);
    dfs(root.right, depth + 1);
}

// LC 104 — Bottom-Up: children return their depth, parent adds 1
public int maxDepth_bottomUp(TreeNode root) {
    if (root == null) return 0;

    // Post-order: solve children FIRST
    int leftDepth  = maxDepth_bottomUp(root.left);
    int rightDepth = maxDepth_bottomUp(root.right);

    // Combine: take max of children, add 1 for current node
    return 1 + Math.max(leftDepth, rightDepth);
}

Use TOP-DOWN when:
  → You need to pass parent/ancestor info to children
  → Path tracking: carry path, sum, or max-so-far downward
  → Early termination: can stop when condition met at a node
  → Examples: LC 112 (Path Sum), LC 129 (Sum Root to Leaf),
              LC 1448 (Count Good Nodes), LC 257 (Binary Tree Paths)

Use BOTTOM-UP when:
  → Answer depends on BOTH children's results
  → Need to compute subtree properties (height, size, balance)
  → Validation: check property holds for entire subtree
  → Examples: LC 104 (Max Depth), LC 110 (Balanced Tree),
              LC 543 (Diameter), LC 124 (Max Path Sum),
              LC 236 (LCA), LC 652 (Find Duplicate Subtrees),
              LC 968 (Binary Tree Cameras)

// LC 543 — Diameter: bottom-up height + global max update
int diameter = 0;

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

private int height(TreeNode root) {
    if (root == null) return 0;

    int left  = height(root.left);   // bottom-up: get children's height
    int right = height(root.right);

    // Global update: diameter passes THROUGH this node
    diameter = Math.max(diameter, left + right);

    // Return value: height of subtree (for parent to use)
    return 1 + Math.max(left, right);
}

When to use which traversal:

1. No specific root processing needed?
   → Any order works (preorder/inorder/postorder)

2. Need parent data for children?
   → Use PREORDER (root → left → right)

3. Need children data for parent?
   → Use POSTORDER (left → right → root)

4. Processing sorted data (BST)?
   → Use INORDER (left → root → right)

5. Level-by-level processing?
   → Use BFS/Level-order traversal

6. Need to move upward (to parent) or explore all directions?
   → Use MOVE PARENT pattern (Build parent map + BFS)

7. Need to compare or identify subtrees?
   → Use NODE PATH pattern (Subtree serialization with post-order)

private void getLeafSeq(TreeNode root, List<Integer> list) {
    if (root == null) return;

    // Check leaf BEFORE recursing into children
    if (root.left == null && root.right == null) {
        list.add(root.val);
        return;  // ← Early exit: skip 2 unnecessary null-child calls
    }

    getLeafSeq(root.left, list);
    getLeafSeq(root.right, list);
}

private void getLeafSeq(TreeNode root, List<Integer> list) {
    if (root == null) return;

    getLeafSeq(root.left, list);   // ← calls null, returns immediately
    getLeafSeq(root.right, list);  // ← calls null, returns immediately

    // Check leaf AFTER recursing (children were both null)
    if (root.left == null && root.right == null) {
        list.add(root.val);
    }
}

# python
# LC 94 - Binary Tree Inorder Traversal
# IDEA: thread each node's in-order predecessor back to it; follow the thread up instead of popping a stack
# time = O(n), space = O(1)   output list not counted
def inorderTraversal(root):
    result = []
    curr = root
    while curr:
        if curr.left is None:
            result.append(curr.val)          # nothing on the left: emit, go right
            curr = curr.right
            continue
        pred = curr.left                     # find the in-order predecessor
        while pred.right is not None and pred.right is not curr:
            pred = pred.right
        if pred.right is None:               # first visit: make the thread, go left
            pred.right = curr
            curr = curr.left
        else:                                # second visit: we came back up the thread
            pred.right = None                # restore the tree
            result.append(curr.val)
            curr = curr.right
    return result

// java
// LC 94 - Binary Tree Inorder Traversal
// IDEA: thread each node's in-order predecessor back to it; follow the thread up instead of popping a stack
// time = O(n), space = O(1)   output list not counted
public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    TreeNode curr = root;
    while (curr != null) {
        if (curr.left == null) {
            result.add(curr.val);            // nothing on the left: emit, go right
            curr = curr.right;
            continue;
        }
        TreeNode pred = curr.left;           // find the in-order predecessor
        while (pred.right != null && pred.right != curr) {
            pred = pred.right;
        }
        if (pred.right == null) {            // first visit: make the thread, go left
            pred.right = curr;
            curr = curr.left;
        } else {                             // second visit: we came back up the thread
            pred.right = null;               // restore the tree
            result.add(curr.val);
            curr = curr.right;
        }
    }
    return result;
}

tree   2          curr  pred   action                       out
      / \         2     1      1.right = 2, go left         []
     1   3        1     -      no left: emit, go right (2)  [1]
                  2     1      1.right is 2: cut, emit       [1, 2]
                  3     -      no left: emit, go right       [1, 2, 3]

# python
# LC 114 - Flatten Binary Tree to Linked List
# IDEA: Morris REWIRE - splice the right subtree onto the left subtree's rightmost node, permanently
# time = O(n), space = O(1)
def flatten(root):
    curr = root
    while curr:
        if curr.left:
            # find left subtree's rightmost node (in-order predecessor)
            rightmost = curr.left
            while rightmost.right:
                rightmost = rightmost.right
            # splice: predecessor.right -> original right subtree (PERMANENT, not restored)
            rightmost.right = curr.right
            curr.right = curr.left   # move left subtree to the right
            curr.left = None         # clear left
        curr = curr.right            # advance down the new right spine

   curr                 curr
   /  \                    \
  L    R     ───►          L            (curr.right = curr.left)
   \                        \
    ...                     ...
      \                       \
     L_rightmost            L_rightmost
                              \
                               R         (L_rightmost.right = R)

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

# Create a simple tree
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

// Java TreeNode Class
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

Problem Analysis Decision Tree:

1. Need to process all nodes?
   ├── Yes: Choose appropriate traversal (preorder/inorder/postorder/level-order)
   └── No: Continue

2. Need information from children for parent?
   ├── Yes: Use POSTORDER traversal
   └── No: Continue

3. Need information from parent for children?
   ├── Yes: Use PREORDER traversal
   └── No: Continue

4. Processing level by level?
   ├── Yes: Use BFS/Level-order traversal
   └── No: Continue

5. Need to move upward (to parent) or explore multi-directionally?
   ├── Yes: Use MOVE PARENT pattern (Build parent map + BFS)
   └── No: Continue

6. Need to compare or find duplicate subtrees?
   ├── Yes: Use NODE PATH pattern (Subtree serialization)
   └── No: Continue

7. Working with BST and need sorted order?
   ├── Yes: Use INORDER traversal
   └── No: Use any suitable approach

# python
# LC 1483 - Kth Ancestor of a Tree Node
# IDEA: up[j][v] = the 2^j-th ancestor of v; any k is a sum of powers of two, so jump once per set bit
# time = O(n log n) build, O(log n) per query; space = O(n log n)
from collections import deque

class TreeAncestor:
    def __init__(self, n, parent):
        self.LOG = max(1, n.bit_length())
        self.up = [parent[:]]                    # up[0][v] = direct parent, -1 above the root
        for j in range(1, self.LOG):
            prev = self.up[j - 1]
            row = [-1] * n
            for v in range(n):
                mid = prev[v]
                if mid != -1:
                    row[v] = prev[mid]           # 2^j = 2^(j-1) + 2^(j-1)
            self.up.append(row)
        # depth of every node, for lca(); parent[i] is not guaranteed < i, so BFS from the root
        children = [[] for _ in range(n)]
        root = 0
        for v, p in enumerate(parent):
            if p == -1:
                root = v
            else:
                children[p].append(v)
        self.depth = [0] * n
        queue = deque([root])
        while queue:
            u = queue.popleft()
            for c in children[u]:
                self.depth[c] = self.depth[u] + 1
                queue.append(c)

    def getKthAncestor(self, node, k):
        j = 0
        while k and node != -1:
            if k & 1:
                node = self.up[j][node] if j < self.LOG else -1
            k >>= 1
            j += 1
        return node

    def lca(self, u, v):
        if self.depth[u] < self.depth[v]:
            u, v = v, u
        u = self.getKthAncestor(u, self.depth[u] - self.depth[v])   # same depth first
        if u == v:
            return u
        for j in range(self.LOG - 1, -1, -1):    # largest jumps first, never onto a common node
            if self.up[j][u] != self.up[j][v]:
                u = self.up[j][u]
                v = self.up[j][v]
        return self.up[0][u]

// java
// LC 1483 - Kth Ancestor of a Tree Node
// IDEA: up[j][v] = the 2^j-th ancestor of v; any k is a sum of powers of two, so jump once per set bit
// time = O(n log n) build, O(log n) per query; space = O(n log n)
class TreeAncestor {
    private final int LOG;
    private final int[][] up;

    public TreeAncestor(int n, int[] parent) {
        LOG = Math.max(1, 32 - Integer.numberOfLeadingZeros(n));   // bit length of n
        up = new int[LOG][n];
        up[0] = parent.clone();                  // up[0][v] = direct parent, -1 above the root
        for (int j = 1; j < LOG; j++) {
            for (int v = 0; v < n; v++) {
                int mid = up[j - 1][v];
                up[j][v] = (mid == -1) ? -1 : up[j - 1][mid];   // 2^j = 2^(j-1) + 2^(j-1)
            }
        }
    }

    public int getKthAncestor(int node, int k) {
        for (int j = 0; k > 0 && node != -1; j++, k >>= 1) {
            if ((k & 1) == 1) {
                node = (j < LOG) ? up[j][node] : -1;
            }
        }
        return node;
    }
}

parent = [-1, 0, 0, 1, 1, 2, 2]          getKthAncestor(6, 3):  k = 3 = 0b11
        0                                 bit 0 set: node = up[0][6] = 2
       / \                                bit 1 set: node = up[1][2] = -1  (2's grandparent)
      1   2          up[1] = [-1,-1,-1,0,0,0,0]
     / \ / \                              -> -1: node 6 has only 2 ancestors
    3  4 5  6

# python
# IDEA: two passes; the second moves the root across each edge and adjusts the answer by subtree size
# time = O(n), space = O(n)
# pass 1 (children first) roots the tree at 0: size[u] = nodes under u, ans[0] = sum of depths.
# pass 2 (parents first) moves the root across edge u -> v: the size[v] nodes under v get 1 closer,
# the other n - size[v] get 1 farther, so ans[v] = ans[u] - size[v] + (n - size[v]).
# LC 834 - Sum of Distances in Tree
def sumOfDistancesInTree(n, edges):
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)

    # one iterative DFS from 0 records a parents-before-children order (no recursion limit)
    order, parent = [], [-1] * n
    seen = [False] * n
    seen[0] = True
    stack = [0]
    while stack:
        u = stack.pop()
        order.append(u)
        for v in graph[u]:
            if not seen[v]:
                seen[v] = True
                parent[v] = u
                stack.append(v)

    size = [1] * n
    ans = [0] * n
    for u in reversed(order):                    # pass 1: children before parents
        for v in graph[u]:
            if v != parent[u]:
                size[u] += size[v]
                ans[u] += ans[v] + size[v]       # every node under v is 1 deeper from u

    for u in order:                              # pass 2: parents before children
        for v in graph[u]:
            if v != parent[u]:
                ans[v] = ans[u] - size[v] + (n - size[v])
    return ans

// java
// IDEA: two passes; the second re-roots across each edge and adjusts the answer by subtree size
// time = O(n), space = O(n)
// pass 1 roots the tree at 0 (size[], ans[0]); pass 2: ans[v] = ans[u] - size[v] + (n - size[v])
// LC 834 - Sum of Distances in Tree
public int[] sumOfDistancesInTree(int n, int[][] edges) {
    List<List<Integer>> graph = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        graph.add(new ArrayList<>());
    }
    for (int[] e : edges) {
        graph.get(e[0]).add(e[1]);
        graph.get(e[1]).add(e[0]);
    }

    // iterative DFS from 0: a parents-before-children order, no recursion depth limit
    int[] order = new int[n];
    int[] parent = new int[n];
    Arrays.fill(parent, -1);
    boolean[] seen = new boolean[n];
    Deque<Integer> stack = new ArrayDeque<>();
    stack.push(0);
    seen[0] = true;
    int idx = 0;
    while (!stack.isEmpty()) {
        int u = stack.pop();
        order[idx++] = u;
        for (int v : graph.get(u)) {
            if (!seen[v]) {
                seen[v] = true;
                parent[v] = u;
                stack.push(v);
            }
        }
    }

    int[] size = new int[n];
    int[] ans = new int[n];
    Arrays.fill(size, 1);
    for (int i = n - 1; i >= 0; i--) {           // pass 1: children before parents
        int u = order[i];
        for (int v : graph.get(u)) {
            if (v != parent[u]) {
                size[u] += size[v];
                ans[u] += ans[v] + size[v];      // every node under v is 1 deeper from u
            }
        }
    }
    for (int i = 0; i < n; i++) {                // pass 2: parents before children
        int u = order[i];
        for (int v : graph.get(u)) {
            if (v != parent[u]) {
                ans[v] = ans[u] - size[v] + (n - size[v]);
            }
        }
    }
    return ans;
}

edges 0-1, 0-2, 2-3, 2-4, 2-5        pass 1 (root 0): size = [6,1,4,1,1,1], ans[0] = 1+1+2+2+2 = 8
      0                              pass 2:
     / \                               ans[1] = 8 - 1 + (6 - 1) = 12
    1   2                              ans[2] = 8 - 4 + (6 - 4) = 6
      / | \                             ans[3] = 6 - 1 + (6 - 1) = 10   (same for 4, 5)
     3  4  5                         -> [8, 12, 6, 10, 10, 10]

# Height (bottom-up, postorder)
def height(node):
    if not node:
        return 0
    return 1 + max(height(node.left), height(node.right))

# Depth (top-down, preorder)
def calculate_depth(node, depth=0):
    if not node:
        return
    
    node.depth = depth  # Assign depth to node
    calculate_depth(node.left, depth + 1)
    calculate_depth(node.right, depth + 1)

class Solution:
    def __init__(self):
        self.max_sum = float('-inf')  # Global result
    
    def max_path_sum(self, root):
        def dfs(node):
            if not node:
                return 0
            
            left_max = max(0, dfs(node.left))   # Ignore negative paths
            right_max = max(0, dfs(node.right))
            
            # Update global maximum
            self.max_sum = max(self.max_sum, node.val + left_max + right_max)
            
            # Return maximum path through this node
            return node.val + max(left_max, right_max)
        
        dfs(root)
        return self.max_sum