112. Path Sum

Easy

Description

給定一棵二元樹和一個目標值 targetSum，判斷是否存在一條從根到葉子節點的路徑，使得路徑上所有節點值的總和等於 targetSum。

Example:

Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22 Output: true (路徑 5 -> 4 -> 11 -> 2 = 22)

Intuition#

從根往下走，每經過一個節點就將目標值減去該節點值，到達葉子時檢查是否剛好為零。

遞迴傳遞「剩餘目標值」，每層減去當前節點值
注意必須走到葉子節點（左右子節點都為 null）才能判斷

Approaches#

⭐ 1: Recursive DFS#

概念: 遞迴地將 targetSum 減去當前節點值，到葉子節點時檢查是否為 0
時間複雜度: O(n)，最差情況需要遍歷所有節點
空間複雜度: O(h)，遞迴堆疊深度

class Solution {
    fun hasPathSum(root: TreeNode?, targetSum: Int): Boolean {
        if (root == null) return false
        val remaining = targetSum - root.`val`
        if (root.left == null && root.right == null) {
            return remaining == 0
        }
        return hasPathSum(root.left, remaining) || hasPathSum(root.right, remaining)
    }
}

2: Iterative DFS with Stack#

概念: 用 Stack 存放節點與剩餘目標值的配對，模擬遞迴過程
時間複雜度: O(n)
空間複雜度: O(h)

class Solution {
    fun hasPathSum(root: TreeNode?, targetSum: Int): Boolean {
        if (root == null) return false
        val stack = ArrayDeque<Pair<TreeNode, Int>>()
        stack.addLast(root to targetSum)
        while (stack.isNotEmpty()) {
            val (node, remaining) = stack.removeLast()
            val newRemaining = remaining - node.`val`
            if (node.left == null && node.right == null && newRemaining == 0) {
                return true
            }
            node.left?.let { stack.addLast(it to newRemaining) }
            node.right?.let { stack.addLast(it to newRemaining) }
        }
        return false
    }
}

🔑 Takeaways#

Pattern: 路徑和問題 — 遞迴傳遞剩餘值，到葉子節點時做判斷
關鍵技巧: 「葉子節點」的判斷是左右子節點都為 null，不要忘記這個條件