112. Path Sum

題目 / Problem

中文： 給定一棵二元樹的根節點 root 和一個整數 targetSum。如果樹中存在一條從根到葉子的路徑，使得路徑上所有節點的值加起來恰好等於 targetSum，就回傳 true；否則回傳 false。葉子是指沒有任何子節點的節點。

English: Given the root of a binary tree and an integer targetSum, return true if there is a root-to-leaf path whose node values add up exactly to targetSum. A leaf is a node with no children.

Constraints / 限制： - 節點數量在 [0, 5000] 範圍內 / Number of nodes is in [0, 5000]. - -1000 <= Node.val <= 1000 - -1000 <= targetSum <= 1000

Worked example / 範例：

root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
Output: true

路徑 5 → 4 → 11 → 2 的總和是 5 + 4 + 11 + 2 = 22，剛好等於目標，所以回傳 true。 The path 5 → 4 → 11 → 2 sums to 22, which matches the target, so the answer is true.

名詞解釋 / Glossary

• 二元樹 / binary tree：一種樹狀資料結構，每個節點最多有兩個子節點，分別叫做左子節點 (left) 和右子節點 (right)。A tree structure where each node has at most two children, named left and right.
• 節點 / node：樹裡的一個元素，包含一個值 (val) 和兩個指向子節點的指標 (left、right)。An element of the tree holding a value and two pointers to its children.
• 葉子節點 / leaf node：left 和 right 都是空 (NULL / nullptr) 的節點，也就是路徑的終點。A node whose left and right are both empty — the end of a path.
• 根到葉子路徑 / root-to-leaf path：從最頂端的根節點一路往下走到某個葉子節點，中間經過的所有節點連成的序列。The sequence of nodes from the top root all the way down to a leaf.
• 深度優先搜尋 / DFS (Depth-First Search)：一種走訪樹的方法，沿著一條路走到底，再回頭走別條。這裡我們用它把每條根到葉的路徑都試一遍。A traversal that goes as deep as possible along one branch before backtracking to try others.
• 遞迴 / recursion：函式呼叫自己來解決更小的子問題。走訪左子樹和右子樹時，我們對子節點呼叫同一個函式。A function calling itself to solve smaller subproblems — here, on each child subtree.
• 指標 / pointer（C）：一個存放「記憶體位址」的變數。struct TreeNode *root 就是指向一個節點的指標；用 root->val 取出它的值。A variable that stores a memory address; root->val reads the value the pointer points to.

思路

最直覺的暴力想法是：把每一條從根到葉的路徑都完整走出來，記下路徑上的所有值，走到葉子時把它們加起來看看是不是等於 targetSum。這樣做是對的，但要額外存整條路徑，稍嫌麻煩。我們可以更聰明一點：不需要記住整條路徑，只要在往下走的過程中，把「還差多少才湊到目標」一路傳下去就好。具體做法是——每經過一個節點，就用剩餘目標減掉這個節點的值，得到一個新的「剩餘目標」交給子節點。當我們走到一個葉子節點（左右子樹都是空）時，只要檢查此刻的剩餘目標是不是剛好等於這個葉子的值，是的話就代表整條路徑加起來等於原始目標，回傳 true。這用遞迴實作非常自然：對每個節點，我們問「左子樹能不能湊出剩下的量，或右子樹能不能湊出剩下的量」，兩者只要有一邊成立就成立。關鍵不變量是：呼叫某節點時傳入的 targetSum，永遠代表「從這個節點到葉子這段還需要湊出的總和」。要特別小心的一點是——一定要走到葉子才能判定成功，不能在半路一個非葉節點就因為剩餘量歸零而回傳 true，因為題目要求的是完整的根到葉路徑。

The brute-force idea is to walk out every root-to-leaf path in full, collect all the values along it, and at each leaf check whether they sum to targetSum. That works but wastes effort storing the whole path. A cleaner trick: instead of tracking the path, carry down a running "remaining target." Each time we visit a node, subtract its value from the remaining target and hand the new remainder to its children. When we reach a leaf (both children empty), we just check whether the remaining target now equals that leaf's value — if so, the whole path summed to the original target and we return true. This maps perfectly onto recursion: for any node we ask "can the left subtree make up the rest, OR can the right subtree make up the rest?" and either one succeeding is enough. The invariant is that the targetSum passed into a node always means "the sum still needed from this node down to a leaf." The one subtle rule: success can only be declared at a leaf — we must not return true at an internal node just because the remainder hit zero, since the problem demands a complete root-to-leaf path.

逐步走查 / Walkthrough

Example: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22. We follow the winning path 5 → 4 → 11 → 2. At each call, need = sum still required from this node down.

第 5 步走到葉子 2，此時 need 恰好等於 2，回傳 true。這個 true 會一路往上傳回給根節點，最終整個函式回傳 true。 At step 5 we hit leaf 2 with need == 2, returning true. That true bubbles back up through every recursive call to the root, so the final answer is true.

Solution — C

/*
 * 演算法 / Algorithm:
 *   深度優先搜尋 + 遞迴。每往下一層就從 targetSum 減去目前節點的值，
 *   把「還需要湊多少」傳給子節點；走到葉子時檢查剩餘量是否等於葉子值。
 *   DFS with recursion: subtract each node's value from targetSum as we
 *   descend, then at a leaf check whether the remainder equals the leaf's value.
 */

/**
 * struct TreeNode 由 LeetCode 事先定義好 / Provided by LeetCode:
 *   struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; };
 */
bool hasPathSum(struct TreeNode* root, int targetSum) {
    // 空樹沒有任何路徑，直接回傳 false / An empty tree has no path at all.
    // root == NULL 表示這裡沒有節點（NULL 是「空指標」）。
    // root == NULL means there is no node here (NULL is the "null pointer").
    if (root == NULL) {
        return false;
    }

    // 用 -> 取出指標所指節點的成員 / '->' reads a member through a pointer.
    // 判斷是否為葉子：左右子節點都是空。
    // Check for a leaf: both children are empty.
    if (root->left == NULL && root->right == NULL) {
        // 到了葉子，這條路徑成立當且僅當剩餘目標剛好等於葉子的值。
        // At a leaf, the path works exactly when the remaining target equals this value.
        return targetSum == root->val;
    }

    // 還不是葉子：把「扣掉目前值後的新目標」往下傳給兩邊子樹。
    // Not a leaf yet: pass the reduced target down to both subtrees.
    int remaining = targetSum - root->val;  // 剩餘要湊的量 / sum still needed below

    // 左子樹或右子樹只要有一邊能湊成，就回傳 true。
    // If EITHER the left or the right subtree can make it up, return true.
    // || 是「邏輯或」，只要左邊為 true 就會短路，不再算右邊。
    // '||' is logical OR; if the left is true it short-circuits and skips the right.
    return hasPathSum(root->left, remaining) || hasPathSum(root->right, remaining);
}

Solution — C++

/*
 * 演算法 / Algorithm:
 *   與 C 版相同：DFS + 遞迴。往下遞減 targetSum，葉子處比對剩餘量。
 *   Same as the C version: DFS with recursion; decrement targetSum going down
 *   and compare the remainder at each leaf.
 */

/**
 * Definition provided by LeetCode / LeetCode 已提供:
 *   struct TreeNode {
 *       int val;
 *       TreeNode *left;
 *       TreeNode *right;
 *   };
 */
class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        // 空節點：沒有路徑，回傳 false / Null node: no path here, return false.
        // nullptr 是 C++ 的空指標（比 C 的 NULL 更型別安全）。
        // nullptr is C++'s null pointer (more type-safe than C's NULL).
        if (root == nullptr) {
            return false;
        }

        // 葉子判斷：兩個子節點都是 nullptr。
        // Leaf check: both children are nullptr.
        if (root->left == nullptr && root->right == nullptr) {
            // 葉子處：剩餘目標是否剛好等於這個葉子的值。
            // At the leaf: does the remaining target equal this leaf's value?
            return targetSum == root->val;
        }

        // 非葉子：計算傳給子節點的新目標。
        // Internal node: compute the new target to pass to children.
        int remaining = targetSum - root->val;  // 還需湊出的總和 / remaining sum needed

        // 左右子樹任一邊成功即可；|| 會短路以節省計算。
        // Either subtree succeeding is enough; '||' short-circuits to save work.
        return hasPathSum(root->left, remaining) ||
               hasPathSum(root->right, remaining);
    }
};

複雜度 / Complexity

• Time: O(n) — n 是節點總數。遞迴會拜訪每個節點恰好一次，每次只做常數量的比較與減法。最壞情況（例如整棵樹歪成一條鏈）也還是每個節點各一次。n is the number of nodes; recursion visits each node exactly once, doing O(1) work per node.
• Space: O(h) — h 是樹的高度，來自遞迴呼叫堆疊的深度。平衡樹時 h ≈ log n，最壞情況（退化成鏈狀）時 h = n。h is the tree height; space comes from the recursion call stack. Balanced ⇒ O(log n), worst case (a chain) ⇒ O(n).

Pitfalls & Edge Cases

• 空樹 / Empty tree（root == NULL）：必須先處理，直接回傳 false。即使 targetSum 是 0 也一樣，因為沒有任何根到葉路徑存在（見範例 3）。Handle first and return false — even when targetSum == 0, because no root-to-leaf path exists.
• 不能在非葉節點提前回傳 true / Don't succeed at an internal node：只有走到葉子才可以判定成功。如果剩餘量在半路歸零就回傳 true，會錯誤接受一條沒走到底的路徑。Only a leaf can confirm success; declaring victory mid-path accepts an incomplete path.
• 負數值 / Negative values：節點值可以是負的（-1000 <= val），所以剩餘目標可能先變大又變小。不要用「剩餘量 < 0 就剪枝」這種假設，那對含負值的樹是錯的。Values can be negative, so the remainder may go up and down — don't prune on "remainder < 0."
• 只有一個子節點的節點 / Node with a single child：這種節點不是葉子，不能在此判斷成功。程式碼用「左右都為空」的嚴格條件正確排除了它。A node with one child is not a leaf; the strict "both children null" test correctly excludes it.
• 溢位 / Overflow：因為節點數 ≤ 5000 且每個值 ≤ 1000，累計和不會超過 int 範圍，這裡不需要 long。With ≤ 5000 nodes and values ≤ 1000, sums stay within int; no need for long.