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

public class Solution {
    /**
     * 给定一个二叉树root和一个值 sum ，判断是否有从根节点到叶子节点的节点值之和等于 sum 的路径
     *
     *
     * @param root TreeNode类
     * @param sum int整型
     * @return bool布尔型
     */
    public boolean hasPathSum (TreeNode root, int sum) {
        if (null == root) {
            return false;
        }
        if (sum - root.val == 0 && isLeafNode(root)) {
            return true;
        }
        return  hasPathSum(root.left, sum - root.val) ||
                hasPathSum(root.right, sum - root.val);
    }

    /**
     * 判断节点是不是叶子节点
     *
     *
     * @param node TreeNode类
     * @return bool布尔型
     */
    public boolean isLeafNode(TreeNode node) {
        return null == node.left && null == node.right;
    }

}

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

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

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

public boolean hasPathSum (TreeNode root, int sum) {
        // write code here
        if (root == null) {
            return false;
        }
        return process(root, sum);
    }

    private boolean process(TreeNode root, int target) {
        if (root.left == null && root.right == null) {
            return root.val == target;
        }
        boolean left = false;
        boolean right = false;
        if (root.left != null) {
            left = process(root.left, target - root.val);
        }
        if(root.right != null) {
            right = process(root.right, target - root.val);
        }
        return left | right;
    }

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @param sum int整型
     * @return bool布尔型
     */
    // class Sum {
    //     TreeNode node = null;
    //     int sum = 0;
    //     Sum(TreeNode node, int sum) {
    //         this.sum = sum;
    //         this.node = node;
    //     }
    // }
    // public boolean hasPathSum (TreeNode root, int sum) {
    //     // write code here
    //     Queue<Sum> que = new ArrayDeque<>();
    //     if (root == null) return false;
    //     Sum temp = new Sum(root, root.val);
    //     que.add(temp);
    //     while (!que.isEmpty()) {
    //         Sum t = que.poll();
    //         if (t.node.left != null) {
    //             que.add(new Sum(t.node.left, t.sum + t.node.left.val));
    //         }
    //         if (t.node.right != null) {
    //             que.add(new Sum(t.node.right, t.sum + t.node.right.val));
    //         }
    //         if(t.node.right==null&&t.node.left==null&&t.sum==sum){
    //             return true;
    //         }
    //     }
    //     return false;
    // }
    public boolean hasPathSum (TreeNode root, int sum) {
        if (root == null) return false;
        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);
    }

}

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布尔型
     */
    List<List<Integer>> ans=new LinkedList<>();
    LinkedList<Integer> path=new LinkedList<>(); 
    public boolean hasPathSum (TreeNode root, int sum) {
        //回溯，统计叶子节点的路径和
        boolean ansss=false;
        build(root,sum);
        if (ans.isEmpty()==true){
            return false;
        }else {
            return true;
        }
         
    }
    public void build(TreeNode root,int sum){
        if(root==null){
            return ;
        }
        path.add(root.val);
        sum=sum-root.val;
        if(sum==0&&root.left==null&&root.right==null){
            ans.add(new LinkedList<>(path));
        }
        build(root.left,sum);
        build(root.right,sum);
        path.removeLast();
    }
    
}

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 isHasPathSum(root,sum,0);

    }

    private boolean isHasPathSum(TreeNode root, int sum, int temp) {
        if (root == null) {
            return false;
        }
        if(root.left == null && root.right == null) {
            return sum == root.val+temp;
        }
        boolean r1 = isHasPathSum(root.left, sum, root.val + temp);
        if (r1) {
            return r1;
        }
        boolean r2 = isHasPathSum(root.right, sum, root.val + temp);
        return r2;
    }



}

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
        return dfs(root,sum);
    }
    boolean dfs(TreeNode root, int num) {
        if (root == null)
            return false;
        num -= root.val;
        if (root.left == null && root.right == null && num == 0)
            return true;
        return dfs(root.left,num) || dfs(root.right,num);
        }
}

public boolean hasPathSum (TreeNode root, int sum) {
    // 递归终止条件
    if (root == null) return false;
    if (root.left == null && root.right == null && root.val == sum) return true;
    // 判断左子树的路径和=sum-root.val
    // 判断右子树的路径和=sum-root.val
    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;
        List<Integer> list = new ArrayList();
        visit(root,0,list);
        return list.contains(new Integer(sum));
    }
    
    
    private void visit(TreeNode root,int count,List<Integer> list){
        count = count + root.val;
        if(root.left==null&&root.right==null) list.add(count);
        if(root.left!=null)visit(root.left,count,list);
        if(root.right!=null)visit(root.right,count,list);
        
    }
}

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布尔型
     */
    boolean tag = false;
    public boolean hasPathSum (TreeNode root, int sum) {
        // write code here
        bfs(root, 0, sum);
        return tag;
    }

    public void bfs(TreeNode root, int count, int target) {
        if (root == null) return;
        if (root.left == null && root.right == null && root.val + count == target) {
            tag = true;
            return;
        }

        bfs(root.left, count + root.val, target);
        bfs(root.right, count + root.val, target);
    }
}

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;
        }
        
        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) {
        // write code here
        return midtraversel(root,sum);
    }
    
     public boolean midtraversel(TreeNode root, int sum){
         if (root == null) return false;
         if (root.left == null && root.right == null) {
            if (sum-root.val != 0 ) return false;
            return true;
        }
        return  midtraversel(root.left,sum - root.val) || midtraversel(root.right,sum-root.val);
    }
}

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

import java.util.*;
public class Solution {
    //深度遍历路径中节点值叠加
    static int add = 0;
    //root到当前节点总共的叠加次数
    static int count = 0;
    static boolean flag = false;
    static int temp = 0;
    public void dfs(TreeNode node, int sum) {
        if (node == null ) {
            if (add == sum && count > 1) {
                flag = true;
            }
            return;
        }
        add += node.val;
        count++;
        temp = node.val;
        dfs(node.left, sum);
        dfs(node.right, sum);
        //回溯
        add -= node.val;
        count--;
    }
    public boolean hasPathSum (TreeNode root, int sum) {
        // 特殊情况判断
        if (root == null) return false;
        if (root.left == null && root.right == null) {
            if (root.val == sum) {
                return true;
            } else {
                return false;
            }
        }
        //进入dfs递归
        dfs(root, sum);
        return flag;
    }
}