题解 | #二叉树中是否存在节点和为指定值的路径#

题目：二叉树中是否存在节点和为指定值的路径

描述：给定一个二叉树和一个值 sum，判断是否有从根节点到叶子节点的节点值之和等于 sum的路径，例如：给出如下的二叉树， sum=22，

返回true，因为存在一条路径5→4→11→2的节点值之和为22

示例1：输入：{1,2},0，返回值：false

解法一：

思路分析：首先我们通读题目可以知道，要计算节点和为指定路径，肯定需要进行遍历操作，将二叉树的元素进行遍历分为三种情况考虑：
第一种：当root == nullptr，即root都不存在，可直接返回false；

第二种：当root的值正好等于sum的值，且其左右子树均为空，直接返回true；

第三种：用sum的值减去root的值，继续在root的左右子树中进行遍历操作。

实例分析：如上图实例

具体C++程序为：

/**
 * struct TreeNode {
 *    int val;
 *    struct TreeNode *left;
 *    struct TreeNode *right;
 * };
 */
 
class Solution {
public:
    /**
     *
     * @param root TreeNode类
     * @param sum int整型
     * @return bool布尔型
     */
    bool hasPathSum(TreeNode* root, int sum) {
        // write code here
        if(root == nullptr)
            return false;
        else if(root->val == sum && root->left == nullptr && root->right == nullptr)
            return true;
        return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right , sum - root->val);//继续遍历循环
    }
};

这个程序是从root的两边同时开始查找，只要有一方返回true，结果就直接返回true，所以其时间复杂度为O(N)，空间复杂度为O(1)。

解法二：

思路分析：二叉树根节点到叶子结点和为指定值的路径，因为不需要保存每一条满足的路径，如果有一条路径满足指定值，就可以返回最终结果值true，我们使用一个flag变量表示是否找到满足题意的路径和，在遍历每一条路径的时候，遍历每一个结点，把当前结点的值加入到路径和当中，假如到叶子结点所求的路径等于sum，那么就将flag改为true。

具体C++代码为：

/**
 * struct TreeNode {
 *    int val;
 *    struct TreeNode *left;
 *    struct TreeNode *right;
 * };
 */
 
class Solution {
public:
    /**
     *
     * @param root TreeNode类
     * @param sum int整型
     * @return bool布尔型
     */
    bool flag = false;//全局变量
    bool hasPathSum(TreeNode* root, int sum) {
        // write code here、
        panduan(root, sum, 0);
        return flag;
    }
    void panduan(TreeNode* root,int sum,int add){
        if(root == nullptr || flag == true)
            return;
        add += root->val;//存储路径和
        if(root->left == NULL && root->right == NULL){
            if(sum == add)//是否与sum相等
                flag = true;
        }
        else{
            panduan(root->left,sum,add);//递归左子树
            panduan(root->right,sum,add);//递归右子树
        }
    }
};

该程序需要不断的递归左右子树，故时间复杂度为O(N)，空间复杂度为O(N)。