算法

(DFS) $O(n)$

使用深度搜索的方法，当搜索到叶子节点时，比较与目标和的值，若相同，则结果为真，若搜索完毕没有出现目标和，返回假。

C++ 代码

class Solution {
public:
    bool hasPathSum(TreeNode* root, int sum) {
        if (root == nullptr) return false;
        else if (root->val == sum && !root->left && !root->right)  return true;
        else return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val);
    }
};