Leetcode-112. 路径总和

发表于 分类于 阅读次数：

题目链接：https://leetcode-cn.com/problems/path-sum/

解法1：dfs

思路：

dfs扫描树，没到一个节点sum-=root->val

若sum==0且这个点为叶子节点，则直接返回true

遍历整棵树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    bool hasPathSum(TreeNode* root, int sum) {
        return ok(root,sum);
    }
    bool ok(TreeNode *root,int sum)
    {
        if(root==NULL)
            return false;
        sum-=root->val;
        if(sum==0&&root->left==NULL&&root->right==NULL)
            return true;
        return ok(root->left,sum)||ok(root->right,sum);
    }
};