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

题解一：先序遍历
解题思路：
1.对树进行先序遍历。使用ans路径和。
2.如果ans> sum 或者ans!=sum&&到达叶子节点,那么就回溯(剪枝)
3. 找到合法路径，返回true;
图示：

复杂度分析：
时间复杂度：O(N),二叉树的节点数N
空间复杂度：O(N)，二叉树退化成链表的特殊情况，需要遍历整个树
实现如下:

class Solution {
public:
    /**
     *
     * @param root TreeNode类
     * @param sum int整型
     * @return bool布尔型
     */
    bool hasPathSum(TreeNode* root, int sum) {
        // write code here
        if(!root) return false;//特判根节点为空的情况；
        return pre_order(root,sum,0);
    }
    bool pre_order(TreeNode* root,int sum, int ans){
        if(!root) return false;//先序遍历终止条件；
        ans += root->val;//累和
        if(!root->left&&!root->right&&ans == sum) return true;//当前节点为子节点，并且和为sum，存在节点和为指定值的路径；
        return pre_order(root->left, sum, ans) || pre_order(root->right, sum, ans);//分支分别从左右节点判断是否存在；
    }
};

题解二： 层次遍历
题解思路： 对树进行层次遍历，遍历到叶节点，判断是否有合法路径。
算法分析：
1.首先自定义结构path_sum{TreeNode*, cur_sum}，表示到节点的路径和。
2. 每次遍历一个节点，将当前节点的val值加上父节点的cur_sum，创建一个path_sum加入队列中。
3.如果到了叶节点，某个path_sum的cur_sum属性等于sum的值。
图示：

复杂度分析：
时间复杂度：O(N),最坏为树退化为链表
空间复杂度：O(N),二叉树退化成链表的特殊情况，需要遍历整个树

实现如下:

class Solution {
public:
    /**
     *
     * @param root TreeNode类
     * @param sum int整型
     * @return bool布尔型
     */
    struct path_sum{
        TreeNode* node;
        int cur_sum;
        path_sum(TreeNode* root = NULL, int value = 0):node(root),cur_sum(value){};
    };//自定义path_sum 用于表示到节点的路径和

    bool hasPathSum(TreeNode* root, int sum) {
        if(!root) return false;
        queue<path_sum*> q;
        path_sum* head = new path_sum(root,root->val);  //以头节点构造一个path_sum
        q.push(head);
        //队列不为空
        while(!q.empty()){
            path_sum* tmp = q.front(); // 取出一个path_sum
            q.pop();
            if(tmp->node->left==NULL&&tmp->node->right==NULL) //如果为叶子节点
            {
                if(tmp->cur_sum==sum) return true; //判断与sum的关系
            }else{
                if(tmp->node->left)//如果具有左节点
                {
                    int left_sum = tmp->node->left->val+tmp->cur_sum;
                    path_sum* left = new path_sum(tmp->node->left,left_sum);
                    q.push(left);
                }
                if(tmp->node->right)//如果有右节点
                {
                    int right_sum = tmp->node->right->val+tmp->cur_sum;
                    path_sum* right = new path_sum(tmp->node->right,right_sum);
                    q.push(right);
                }    
            }
        }
        return false;
    }
};