寻找二叉树是否有给定的路径和

向右看齐 2022-05-19 05:45 119阅读 0赞

这里写图片描述

  1. import java.util.ArrayList;
  2. class TreeNode {
  3. int val;
  4. TreeNode left;
  5. TreeNode right;
  6. TreeNode(int x) { val = x; }
  7. }
  8. public class Solution {
  9. ArrayList<ArrayList<Integer>> arr=new ArrayList<ArrayList<Integer>>();
  10. public boolean hasPathSum(TreeNode root, int sum) {
  11. ArrayList<Integer>list=new ArrayList<>();
  12. getPaths(root,sum,list);
  13. return arr.size()>0?true:false;
  14. }
  15. //递归函数实现路径存储
  16. public void getPaths(TreeNode root,int sum,ArrayList<Integer>list){
  17. if(root==null) return;
  18. if(root.left==null&&root.right==null&&sum-root.val==0){
  19. list.add(root.val);
  20. arr.add(new ArrayList<Integer>(list));
  21. list.remove(list.size()-1);
  22. return;
  23. }
  24. list.add(root.val);
  25. getPaths(root.left,sum-root.val,list);
  26. getPaths(root.right,sum-root.val,list);
  27. list.remove(list.size()-1);
  28. }
  29. 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)); } }

发表评论

表情:
评论列表 (有 0 条评论,119人围观)

还没有评论,来说两句吧...

相关阅读