题意

给定一个二叉树，判断是否存在这样的路径：它由根节点到叶子节点，且路径上的节点的值之和等于给定数。

思路

分析题目，我们可以发现：如果存在满足题目要求的路径，那么它所有的节点一定是由二叉树根节点与二叉树左子树或右子树中的一条子路径构成的，而子路径也可以通过这种方法求出，因此我们可以考虑递归与深度优先搜索，只要找到满足条件的路径，就返回$truetrue$，若未找到则返回$falsefalse$。

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @param sum int整型 
     * @return bool布尔型
     */
    bool dfs(TreeNode* now,int ter)
    {
        if(now == NULL) return false;//若当前节点不存在，返回假
        ter -= now->val;//把需要找的值减去当前值
        if(!ter && now->left == NULL && now->right == NULL) return true;
        //若路径之和刚好等于sum，且节点是叶子节点，返回真
        return dfs(now->right,ter)||dfs(now->left,ter);//否则继续搜索左右子树
    }
    bool hasPathSum(TreeNode* root, int sum)
    {
        // write code here
        return dfs(root,sum);//返回搜索结果
    }
};

复杂度分析

时间复杂度：$O(n)O(n)$,$nn$是二叉树的节点个数，每个节点都一定搜索到了。

空间复杂度：$O(H)O(H)$,其中$HH$代表二叉树高度，因为dfs最多只需要搜索$HH$层，因此只需要$O(H)O(H)$的栈空间。