ผลรวมเส้นทางและบรรพบุรุษร่วมที่ใกล้ที่สุด

ผลรวมเส้นทางจากรากถึงโหนดใบ

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

def has_path_sum(root, target):
    if not root:
        return False
    if not root.left and not root.right:  # leaf
        return root.val == target
    remain = target - root.val
    return (has_path_sum(root.left, remain) or
            has_path_sum(root.right, remain))

root = TreeNode(5)
root.left = TreeNode(4)
root.right = TreeNode(8)
root.left.left = TreeNode(11)
root.left.left.left = TreeNode(7)
root.left.left.right = TreeNode(2)
print(has_path_sum(root, 22))  # True: 5->4->11->2

เส้นทางทั้งหมดจากรากถึงโหนดใบ

def all_path_sums(root, target):
    results = []

    def dfs(node, path, remaining):
        if not node:
            return
        path.append(node.val)
        if not node.left and not node.right and remaining == node.val:
            results.append(list(path))  # snapshot
        else:
            dfs(node.left, path, remaining - node.val)
            dfs(node.right, path, remaining - node.val)
        path.pop()  # backtrack

    dfs(root, [], target)
    return results

root = TreeNode(5)
root.left = TreeNode(4)
root.right = TreeNode(8)
root.left.left = TreeNode(11)
root.left.left.right = TreeNode(2)
root.right.right = TreeNode(5)
print(all_path_sums(root, 22))  # [[5,4,11,2]]

ผลรวมเส้นทาง III: เส้นทางใดก็ได้ โหนดใดก็ได้

def path_sum_iii(root, target):
    prefix_counts = {0: 1}

    def dfs(node, running_sum):
        if not node:
            return 0
        running_sum += node.val
        count = prefix_counts.get(running_sum - target, 0)
        prefix_counts[running_sum] = prefix_counts.get(running_sum, 0) + 1
        count += dfs(node.left, running_sum)
        count += dfs(node.right, running_sum)
        prefix_counts[running_sum] -= 1  # backtrack
        return count

    return dfs(root, 0)

root = TreeNode(10)
root.left = TreeNode(5)
root.right = TreeNode(-3)
root.left.left = TreeNode(3)
root.left.right = TreeNode(2)
root.right.right = TreeNode(11)
root.left.left.left = TreeNode(3)
root.left.left.right = TreeNode(-2)
root.left.right.right = TreeNode(1)
print(path_sum_iii(root, 8))  # 3

บรรพบุรุษร่วมที่ใกล้ที่สุดคืออะไร

#       3
#      / \
#     5   1
#    / \ / \
#   6  2 0  8
#     / \
#    7   4
# LCA(5, 1) = 3  (root)
# LCA(5, 4) = 5  (p itself is ancestor of q)
# LCA(6, 4) = 5
# LCA(7, 4) = 2
# Key insight: the LCA is the node where p and q
# first 'split' into different subtrees.
print('LCA: deepest node that is ancestor of both p and q')

อัลกอริทึม LCA แบบเรียกซ้ำ

def lowest_common_ancestor(root, p, q):
    # Base case: empty or found one of the targets
    if not root or root == p or root == q:
        return root
    # Search both subtrees
    left = lowest_common_ancestor(root.left, p, q)
    right = lowest_common_ancestor(root.right, p, q)
    # If both sides found something, this node is the LCA
    if left and right:
        return root
    # Otherwise, return whichever side found something
    return left if left else right

root = TreeNode(3)
root.left = TreeNode(5)
root.right = TreeNode(1)
root.left.left = TreeNode(6)
root.left.right = TreeNode(2)
p, q = root.left, root.right  # 5 and 1
lca = lowest_common_ancestor(root, p, q)
print(lca.val)  # 3

LCA เมื่อโหนดสามารถเป็นบรรพบุรุษของตัวเอง

# Test case: p is ancestor of q
# Tree: 3 -> left=5 -> left=6
# LCA(5, 6) should be 5
root = TreeNode(3)
root.left = TreeNode(5)
root.left.left = TreeNode(6)

p = root.left     # node 5
q = root.left.left  # node 6

lca = lowest_common_ancestor(root, p, q)
print(lca.val)  # 5 (p itself is the LCA)

LCA ด้วยตัวชี้ไปยังโหนดแม่

class NodeWithParent:
    def __init__(self, val, parent=None):
        self.val = val
        self.parent = parent
        self.left = None
        self.right = None

def lca_with_parent(p, q):
    ancestors = set()
    # Collect all ancestors of p
    node = p
    while node:
        ancestors.add(node)
        node = node.parent
    # Walk up from q until we hit a known ancestor
    node = q
    while node:
        if node in ancestors:
            return node
        node = node.parent
    return None

print('With parent pointers: O(h) time and space')

LCA ในต้นไม้ค้นหาแบบทวิภาค

def lca_bst(root, p, q):
    if not root:
        return None
    if p.val < root.val and q.val < root.val:
        return lca_bst(root.left, p, q)  # both in left
    if p.val > root.val and q.val > root.val:
        return lca_bst(root.right, p, q)  # both in right
    return root  # split point = LCA

# Iterative BST LCA (no recursion overhead):
def lca_bst_iter(root, p, q):
    while root:
        if p.val < root.val and q.val < root.val:
            root = root.left
        elif p.val > root.val and q.val > root.val:
            root = root.right
        else:
            return root
    return None

print('BST LCA: O(log n) for balanced trees')

ระยะห่างระหว่างสองโหนด

def find_depth(root, target, depth=0):
    if not root:
        return -1
    if root == target:
        return depth
    left = find_depth(root.left, target, depth + 1)
    if left != -1:
        return left
    return find_depth(root.right, target, depth + 1)

def node_distance(root, p, q):
    lca = lowest_common_ancestor(root, p, q)
    # depth from LCA to p and q
    dp = find_depth(lca, p)
    dq = find_depth(lca, q)
    return dp + dq

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(node_distance(root, root.left.left, root.left.right))  # 2

เส้นทางผลรวมสูงสุดจากรากถึงโหนดใบ

def max_root_to_leaf_sum(root):
    if not root:
        return float('-inf')
    best = [float('-inf')]

    def dfs(node, running):
        running += node.val
        if not node.left and not node.right:  # leaf
            best[0] = max(best[0], running)
            return
        if node.left:
            dfs(node.left, running)
        if node.right:
            dfs(node.right, running)

    dfs(root, 0)
    return best[0]

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(max_root_to_leaf_sum(root))  # 1+2+5 = 8

ผลรวมตัวเลขจากรากถึงโหนดใบ

def sum_numbers(root):
    def dfs(node, num):
        if not node:
            return 0
        num = num * 10 + node.val
        if not node.left and not node.right:  # leaf
            return num
        return dfs(node.left, num) + dfs(node.right, num)

    return dfs(root, 0)

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
print(sum_numbers(root))  # 12 + 13 = 25

root2 = TreeNode(4)
root2.left = TreeNode(9)
root2.right = TreeNode(0)
root2.left.left = TreeNode(5)
root2.left.right = TreeNode(1)
print(sum_numbers(root2))  # 495 + 491 + 40 = 1026

ตรวจสอบความเข้าใจ

ทบทวนบทเรียน