二叉树中和为某一值的路径(一)

public boolean hasPathSum (TreeNode root, int sum) {
        // write code here
       if(root == null) return false;
       if(root.left == null && root.right == null && root.val == sum) return true;
       return hasPathSum(root.left,sum - root.val) || hasPathSum(root.right,sum - root.val);
    }

    public boolean hasPathSum (TreeNode root, int sum) {
        if(root == null) return false;
        // write code here
        return dfs(root,0,sum);
    }
    public boolean dfs(TreeNode root,int prevSum,int sum){
        if(root == null){
            return false;
        }
        int tempSum = prevSum + root.val;
        if(root.left == null && root.right == null){
            return tempSum == sum;
        }else{
            return dfs(root.left,tempSum,sum) || dfs(root.right,tempSum,sum);
        }
    }

    public boolean hasPathSum (TreeNode root, int sum) {
        // 判空
        if(root==null){
            return false;
        }
        // 判断左右子树同时为空的同时，刨除val值的sum是否为0，如果成立说明刚好在叶子结点找到和为指定值的路径
        if(root.left==null && root.right==null && sum-root.val==0){
            return true;
        }
        // 遍历二叉树（先序）
        return hasPathSum(root.left,sum-root.val) || hasPathSum(root.right,sum-root.val);
    }

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @param sum int整型 
     * @return bool布尔型
     */
    public boolean hasPathSum (TreeNode root, int sum) {
        // write code here
        if (root == null)
            return false;
        return dfs(root, sum);
    }
    
    // 二叉树的深度遍历
    public boolean dfs(TreeNode tempNode, int target) {
        if (tempNode == null)
            return false;
        target = target - tempNode.val;
        if (tempNode.left == null && tempNode.right == null && target == 0){
            return true;
        }
        return dfs(tempNode.left, target) || dfs(tempNode.right, target);
    }
}

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @param sum int整型 
     * @return bool布尔型
     */
     int s = 0;
    boolean res = false;

    public boolean hasPathSum(TreeNode root, int sum) {
        dfs(root, sum);
        return res;
    }

    public void dfs(TreeNode root, int sum) {
        if (root == null)
            return;
        s += root.val;
     if (s == sum&&root.left==null&&root.right == null) {
            res = true;
            return;
        }
        if (s !=sum) {
            dfs(root.left, sum);
            dfs(root.right, sum);
            s = s - root.val;
        }
    }
}

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @param sum int整型 
     * @return bool布尔型
     */
    public boolean hasPathSum (TreeNode root, int sum) {
        // write code here
        if(root==null){
            return false;
        }
        return dfs(root,sum);
    }
    public boolean dfs (TreeNode root, int sum){
        if(root==null) return false;
        sum-=root.val;
        if(sum==0&&root.left==null&&root.right==null){
            return true;
        }
        return dfs(root.left,sum)||dfs(root.right,sum);
    }
}

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    //回溯法
    //做选择，进行下一步，撤销选择。
    bool res=false;
    bool hasPathSum(TreeNode *root, int sum) {
        if(root==NULL) return false;
        track(root,sum);
        return res;
    }
    void track(TreeNode *root, int &sum)
    {
        if(root==NULL) return ;
        if(root->left==NULL&&root->right==NULL)
        {
            if(sum==root->val)
            {
                res=true;
            }
        }
        
        if(root->left)
        {
            sum=sum-root->val;
            track(root->left,sum);
            sum=sum+root->val;
        }
        if(root->right)
        {
            sum=sum-root->val;
            track(root->right,sum);
            sum=sum+root->val;
        }
        
    }
};

class Solution {
public:
    bool hasPathSum(TreeNode *root, int sum) {
        if(!root)
        	return false;
        if(root->left == NULL && root->right == NULL && root->val == sum)
        	return true;
        return hasPathSum(root->left , sum - root->val) || hasPathSum(root->right , sum - root->val);   	
    }
};

public class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) {
            return false;
        }
        else if (root.left == null && root.right == null && sum == root.val) {
            return true;
        }
        return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
    }
}

    bool hasPathSum(TreeNode *root, int sum) {
        if (!root) return false;
        if (root->val==sum && !root->left && !root->right) return true;
        return hasPathSum(root->left,sum-root->val) 
            || hasPathSum(root->right,sum-root->val);
    }

//递归求解，当root为空返回false，当到达叶子节点，并且和位sum返回true
//其他情况递归调用左右子树
class Solution {
public:
    bool hasPathSum(TreeNode *root, int sum) {
       if(root == NULL)
           return false;
        if(root->left == NULL && root->right == NULL && sum - root->val == 0)
           return true;
       	return hasPathSum(root->left,sum-root->val) || hasPathSum(root->right,sum-root->val);
    }
};

使用递归求解

public class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null)
            return false;

        sum -= root.val;
        if (sum == 0 && root.left == null && root.right == null)
            return true;

        return hasPathSum(root.left, sum) || hasPathSum(root.right, sum);
    }
}

//后序非递归遍历
    public boolean hasPathSum(TreeNode root, int sum) {
        if(root==null)
            return false;
        Stack<TreeNode> stack =new Stack<>();
        Stack<Integer> flag =new Stack<>();
        Stack<Integer> sumStack =new Stack<>();
        sumStack.push(0);
        while(!stack.isEmpty()||root!=null){
            while(root!=null){
                int total=sumStack.peek()+root.val;
                sumStack.push(total);
                stack.push(root);
                flag.push(0);
                root=root.left;
            }
            while(!stack.isEmpty()&&flag.peek()==1){
                TreeNode tt=stack.pop();
                if(sumStack.pop()==sum&&tt.left==null&&tt.right==null)
                    return true;
                flag.pop();
            }
            if(!stack.isEmpty()){
                TreeNode temp=stack.peek();
                flag.pop();
                flag.push(1);
                root=temp.right;
            }
        }
        return false;
    }
    //递归前序
    public boolean hasPathSum1(TreeNode root, int sum) {
        if(root==null) return false;
        if(root.left==null&&root.right==null&&root.val==sum)
            return true;
        return hasPathSum1(root.left,sum-root.val)||hasPathSum1(root.left,sum-root.val);
    }

深度优先遍历非递归

class Solution {
public:
    bool hasPathSum(TreeNode *root, int sum) {
        if(root==NULL)
            return false;
        vector<pair<TreeNode*,int>>stk;
        stk.push_back(make_pair(root,root->val));
        while(!stk.empty()){
            auto cur=stk.back();
            stk.pop_back();
            if(cur.first->left==NULL&&cur.first->right==NULL&&cur.second==sum)
                return true;
            if(cur.first->left!=NULL)
                stk.push_back(make_pair(cur.first->left,cur.second+cur.first->left->val));
            if(cur.first->right!=NULL)
                stk.push_back(make_pair(cur.first->right,cur.second+cur.first->right->val));
        }
        return false;
    }
};

class Solution {
public:
    bool hasPathSum(TreeNode* root, int sum) {
        if(root==nullptr)
            return false;
        if(root->left==nullptr && root->right==nullptr)
            return root->val == sum;
        return hasPathSum(root->left,sum-root->val) || hasPathSum(root->right,sum-root->val);
    }
};

bool hasPathSum3(TreeNode* root, int sum) { //bfs
        if (!root)
        {
            return false;
        }

        queue<TreeNode*> que;
        queue<int> sum_que;
        que.push(root);
        sum_que.push(root->val);

        while (!que.empty())
        {
            TreeNode* cur = que.front();
            que.pop();
            int ret = sum_que.front();
            sum_que.pop();

            if (cur->left==NULL&&cur->right==NULL&&ret==sum)
            {
                return true;
            }
            if (cur->left)
            {
                que.push(cur->left);
                sum_que.push(ret + cur->left->val);
            }
            if (cur->right)
            {
                que.push(cur->right);
                sum_que.push(ret + cur->right->val);
            }
        }
        return false;

    }