樹 — LeetCode 實戰範例

# python
# LC 545 - Boundary of Binary Tree
# IDEA: root, then the left boundary top-down, the leaves left to right, the right boundary bottom-up;
#       neither boundary walk records a leaf, so no node appears twice
# time = O(n), space = O(h)
def boundaryOfBinaryTree(root):
    if not root:
        return []
    result = [root.val]

    def is_leaf(node):
        return not node.left and not node.right

    def left_boundary(node):               # pre-order: record on the way down
        while node and not is_leaf(node):
            result.append(node.val)
            node = node.left if node.left else node.right

    def leaves(node):                      # every leaf, left to right
        if not node:
            return
        if is_leaf(node):
            result.append(node.val)
            return
        leaves(node.left)
        leaves(node.right)

    def right_boundary(node):              # post-order: record on the way back up
        stack = []
        while node and not is_leaf(node):
            stack.append(node.val)
            node = node.right if node.right else node.left
        while stack:
            result.append(stack.pop())

    if not is_leaf(root):                  # a lone root is not also a leaf
        left_boundary(root.left)
        leaves(root)
        right_boundary(root.right)
    return result

# python
# LC 111 - Minimum Depth of Binary Tree
# IDEA: BFS carrying the depth; the first leaf dequeued is the shallowest
# time = O(n), space = O(w)   w = maximum width of a level; stops at the first leaf
from collections import deque

def minDepth(root):
    if not root:
        return 0
    queue = deque([(root, 1)])
    while queue:
        node, depth = queue.popleft()
        if not node.left and not node.right:   # the first leaf BFS reaches is the shallowest
            return depth
        if node.left:
            queue.append((node.left, depth + 1))
        if node.right:
            queue.append((node.right, depth + 1))

# python
# LC 199 - Binary Tree Right Side View
# IDEA: level-order BFS; record the last node of each level
# time = O(n), space = O(w)
from collections import deque

def rightSideView(root):
    result = []
    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:            # the last node of the level is the one you see
                result.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
    return result

# python
# LC 106 - Construct Binary Tree from Inorder and Postorder Traversal
# IDEA: postorder[-1] is the root; its inorder index splits [lo, hi]; build RIGHT first
# time = O(n), space = O(n)   the index map, plus O(h) recursion
def buildTree(inorder, postorder):
    index_of = {val: i for i, val in enumerate(inorder)}
    post_idx = [len(postorder) - 1]           # next root, read from the END of postorder

    def build_range(lo, hi):                  # the subtree whose inorder slice is [lo, hi]
        if lo > hi:
            return None
        root = TreeNode(postorder[post_idx[0]])
        post_idx[0] -= 1
        mid = index_of[root.val]
        root.right = build_range(mid + 1, hi)  # RIGHT first: postorder read backwards is root, right, left
        root.left = build_range(lo, mid - 1)
        return root

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

# python
# LC 1448 - Count Good Nodes in Binary Tree
# IDEA: pre-order DFS carrying the maximum on the path from the root
# time = O(n), space = O(h)
def goodNodes(root):
    def dfs(node, max_so_far):
        if not node:
            return 0
        good = 1 if node.val >= max_so_far else 0
        max_so_far = max(max_so_far, node.val)   # an int: each call has its own copy
        return good + dfs(node.left, max_so_far) + dfs(node.right, max_so_far)

    return dfs(root, root.val)

# python
# LC 1026 - Maximum Difference Between Node and Ancestor
# IDEA: carry the path's min and max down; at the end of a path the answer is max - min
# time = O(n), space = O(h)
def maxAncestorDiff(root):
    def dfs(node, low, high):
        if not node:
            return high - low                    # the path ended: its widest spread
        low = min(low, node.val)
        high = max(high, node.val)
        return max(dfs(node.left, low, high), dfs(node.right, low, high))

    return dfs(root, root.val, root.val)

# python
# LC 104 - Maximum Depth of Binary Tree
# IDEA: post-order; my depth = 1 + the deeper child's depth
# time = O(n), space = O(h)
def maxDepth(root):
    if not root:
        return 0
    return 1 + max(maxDepth(root.left), maxDepth(root.right))

# python
# LC 110 - Balanced Binary Tree
# IDEA: post-order height; -1 is the "unbalanced" sentinel that short-circuits upward
# time = O(n), space = O(h)
def isBalanced(root):
    def height(node):                      # -1 means "already unbalanced below here"
        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

# python
# LC 110 - Balanced Binary Tree (top-down)
# IDEA: at every node compare the two subtree heights, then recurse into both children
# time = O(n log n) on a balanced tree, O(n^2) upper bound; space = O(h)
def isBalanced(root):
    def height(node):
        if not node:
            return 0
        return 1 + max(height(node.left), height(node.right))

    if not root:
        return True
    if abs(height(root.left) - height(root.right)) > 1:
        return False
    return isBalanced(root.left) and isBalanced(root.right)

# python
# LC 968 - Binary Tree Cameras
# IDEA: post-order DFS returning one of 3 states; the parent makes the decision
# time = O(n), space = O(h)
def minCameraCover(root):
    UNCOVERED, CAMERA, COVERED = 0, 1, 2
    cameras = 0

    def dfs(node):
        nonlocal cameras
        if not node:
            return COVERED                 # so a leaf reports UNCOVERED and its parent acts
        left = dfs(node.left)
        right = dfs(node.right)
        if left == UNCOVERED or right == UNCOVERED:   # test this FIRST
            cameras += 1
            return CAMERA
        if left == CAMERA or right == CAMERA:
            return COVERED
        return UNCOVERED                   # decide nothing: the parent places the camera

    if dfs(root) == UNCOVERED:             # the root has no parent to defer to
        cameras += 1
    return cameras

// java
// LC 968 - Binary Tree Cameras
// IDEA: post-order, 3 states; an uncovered child forces a camera here
// time = O(n), space = O(h)
private static final int UNCOVERED = 0, CAMERA = 1, COVERED = 2;
private int cameras = 0;

public int minCameraCover(TreeNode root) {
    cameras = 0;
    if (dfs(root) == UNCOVERED) {
        cameras++;                              // the root has no parent to defer to
    }
    return cameras;
}

private int dfs(TreeNode node) {
    if (node == null) {
        return COVERED;
    }
    int left = dfs(node.left);
    int right = dfs(node.right);
    if (left == UNCOVERED || right == UNCOVERED) {
        cameras++;
        return CAMERA;
    }
    if (left == CAMERA || right == CAMERA) {
        return COVERED;
    }
    return UNCOVERED;
}

        1
       / \
      2   3
     / \
    4   5
   / \
  6   7

post-order: 6, 7, 4, 5, 2, 3, 1
  6, 7 : both children null (COVERED)  -> UNCOVERED
  4    : left UNCOVERED                -> camera #1, CAMERA
  5    : leaf                          -> UNCOVERED
  2    : left CAMERA, right UNCOVERED  -> the uncovered test wins: camera #2, CAMERA
  3    : leaf                          -> UNCOVERED
  1    : right UNCOVERED               -> camera #3, CAMERA
answer 3

# python
# LC 226 - Invert Binary Tree
# IDEA: post-order; invert both subtrees, then swap them
# time = O(n), space = O(h)
def invertTree(root):
    if not root:
        return None
    left = invertTree(root.left)           # compute BOTH before assigning either
    right = invertTree(root.right)
    root.left = right
    root.right = left
    return root

// java
// LC 226 - Invert Binary Tree
// IDEA: post-order; cache both inverted subtrees, then swap
// time = O(n), space = O(h)
public TreeNode invertTree(TreeNode root) {
    if (root == null) {
        return null;
    }
    TreeNode left = invertTree(root.left);     // cache both results first
    TreeNode right = invertTree(root.right);
    root.left = right;
    root.right = left;
    return root;
}

# python
# LC 114 - Flatten Binary Tree to Linked List
# IDEA: post-order; flatten both sides, splice node -> left chain -> right chain, return the tail
# time = O(n), space = O(h)
def flatten(root):
    def flatten_tail(node):                # flatten node's subtree, return its LAST node
        if not node:
            return None
        left_tail = flatten_tail(node.left)
        right_tail = flatten_tail(node.right)
        if left_tail:                      # splice: node -> left chain -> right chain
            left_tail.right = node.right
            node.right = node.left
            node.left = None
        if right_tail:                     # the tail is the last non-empty box
            return right_tail
        if left_tail:
            return left_tail
        return node

    flatten_tail(root)

flatten_tail(3) -> 3              flatten_tail(4) -> 4
flatten_tail(2): left_tail 3, right_tail 4
                 3.right = 4, 2.right = 3, 2.left = None   => 2 -> 3 -> 4,  return 4
flatten_tail(6) -> 6
flatten_tail(5): no left; right_tail 6                     => 5 -> 6,       return 6
flatten_tail(1): left_tail 4, right_tail 6
                 4.right = 5, 1.right = 2, 1.left = None   => 1 -> 2 -> 3 -> 4 -> 5 -> 6

# python
# LC 617 - Merge Two Binary Trees
# IDEA: walk both trees in lockstep; sum where both exist, reuse the lone subtree otherwise
# time = O(min(n1, n2)), space = O(min(h1, h2))
def mergeTrees(root1, root2):
    if not root1:
        return root2                       # reuse the other subtree as it is
    if not root2:
        return root1
    merged = TreeNode(root1.val + root2.val)
    merged.left = mergeTrees(root1.left, root2.left)
    merged.right = mergeTrees(root1.right, root2.right)
    return merged

# python
# LC 951 - Flip Equivalent Binary Trees
# IDEA: Same Tree, but the children pair may also be matched crosswise
# time = O(n), space = O(h)   values are unique, so at most one pairing can match at each node
def flipEquiv(root1, root2):
    if not root1 or not root2:
        return root1 is root2
    if root1.val != root2.val:
        return False
    same = flipEquiv(root1.left, root2.left) and flipEquiv(root1.right, root2.right)
    flipped = flipEquiv(root1.left, root2.right) and flipEquiv(root1.right, root2.left)
    return same or flipped

# python
# LC 2415 - Reverse Odd Levels of Binary Tree
# IDEA: walk mirror pairs in lockstep; swap their values on odd levels
# time = O(n), space = O(log n)   the tree is perfect, so its height is log n
def reverseOddLevels(root):
    def pair(a, b, level):                 # a and b are mirror positions on the same level
        if not a:                          # perfect tree: a and b are empty together
            return
        if level % 2 == 1:
            a.val, b.val = b.val, a.val
        pair(a.left, b.right, level + 1)   # outer pair
        pair(a.right, b.left, level + 1)   # inner pair

    pair(root.left, root.right, 1)
    return root