112. Path Sum

題目網址：https://leetcode.cn/problems/path-sum/

題意：給一 BT 和一整數 targetSum, 返回是否存在 root-to-leaf 之路徑總和為 targetSum 的 path。

Solution 1：

想法：利用 DFS

class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        if (!root) {
            return false;
        }

        if (root->val == targetSum && !root->left && !root->right) {
            return true;
        }

        return hasPathSum(root->left, targetSum - root->val) ||
               hasPathSum(root->right, targetSum - root->val);
    }
};

• time：$O(n)$ ➔ 遍歷整個 BT
• space：$O(n)$ ➔ 遞迴深度最大長度為 n

Solution 2：

想法：利用 BFS

class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        if (!root) {
            return false;
        }

        queue<pair<TreeNode*, int>> q;
        q.push({root, 0}); // sum 初始設 0, 而非 root->val, 因為等等會加上 root->val

        while (!q.empty()) {
            const auto front = q.front();
            q.pop();

            const TreeNode* curNode = front.first;
            const int curSum = front.second + curNode->val;

            // 若為 leaf
            if (!curNode->left && !curNode->right) {
                if (curSum == targetSum) {
                    return true;
                }
            } else {
                if (curNode->left) {
                    q.push({curNode->left, curSum});
                }

                if (curNode->right) {
                    q.push({curNode->right, curSum});
                }
            }
        }

        return false;
    }
};

• time：$O(n)$ ➔ 遍歷整個 BT
• space：$O(n)$ ➔ q 中的元素不超過 n