LeetCode112—Path Sum

桃扇骨 2022-07-26 04:25 140阅读 0赞

# LeetCode112—Path Sum #

## 原题 ##

> Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.
> 
> For example:  
> Given the below binary tree and sum = 22,  
> 　　　　　　5  
> 　　　　　/ 　　\\  
> 　　　　4　　　　8  
> 　　　/　　　　/　　\\  
> 　　11 　　　13 　　　4  
> 　　/ \\ 　　　　　　　　\\  
> 　7 　 2 　　　　　　　　1  
> return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

## 分析 ##

把所有根到叶子节点的路径push到容器中，当到达叶子节点的时候计算和，如果等于目标值就返回，否则继续搜索。这里就是左右子树只要有任意子树满足条件即可，所以代码中用了或逻辑。

## 代码 ##

class Solution {
    private:
        bool isLeafNode(TreeNode* root)
        {
            if (root->left == NULL&&root->right == NULL)
                return true;
            else
                return false;
        }
        bool dfs(TreeNode *root, vector<int>nodes, int sum)
        {
            if (root == NULL)
                return false;
            nodes.push_back(root->val);
            if (isLeafNode(root))
            {
                int val = accumulate(nodes.begin(), nodes.end(), 0);
                if (sum == val)
                    return true;
                else
                    return false;
            }
            else
            {
                return dfs(root->left, nodes, sum)||dfs(root->right, nodes, sum);
            }
        }
    public:
        bool hasPathSum(TreeNode* root, int sum) {
            if (root == NULL)
                return false;
            vector<int>nodes;
            return dfs(root, nodes, sum);
        }
    };