import java.util.ArrayList;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public class Solution {
ArrayList<ArrayList<Integer>> arr=new ArrayList<ArrayList<Integer>>();
public boolean hasPathSum(TreeNode root, int sum) {
ArrayList<Integer>list=new ArrayList<>();
getPaths(root,sum,list);
return arr.size()>0?true:false;
}
//递归函数实现路径存储
public void getPaths(TreeNode root,int sum,ArrayList<Integer>list){
if(root==null) return;
if(root.left==null&&root.right==null&&sum-root.val==0){
list.add(root.val);
arr.add(new ArrayList<Integer>(list));
list.remove(list.size()-1);
return;
}
list.add(root.val);
getPaths(root.left,sum-root.val,list);
getPaths(root.right,sum-root.val,list);
list.remove(list.size()-1);
}
public static void main(String[]args){ //System.out.println("Hello World!"); TreeNode root=new TreeNode(5); root.left=new TreeNode(4); root.right=new TreeNode(8); root.left.left=new TreeNode(11); root.left.left.left=new TreeNode(7); root.left.left.right=new TreeNode(2); Solution s=new Solution(); System.out.println(s.hasPathSum(root,22)); } }
还没有评论,来说两句吧...