Leetcode 112：路径总和

给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。

说明: 叶子节点是指没有子节点的节点。

思路：遍历存储每条路径。当前节点为叶子节点时，求和。并判断是否等于目标值。

public static boolean hasPathSum(TreeNode root, int targetSum) {if(root==null) return false;List<Integer> path=new ArrayList<>();boolean res=pathSum(root,path,targetSum);    //遍历所有路径，并求和return res;}public static boolean pathSum(TreeNode node, List<Integer> path,int targetSum){path.add(node.val);//先判断是否当前节点是否为叶子节点if(node.left==null && node.right==null){int pathSum=0;for(int i=0;i<path.size();i++){pathSum=pathSum+path.get(i);}if(pathSum==targetSum) return true;}//不为叶子节点时if(node.left!=null){boolean left=pathSum(node.left,path,targetSum);if(left) return true;path.remove(path.size()-1);}if(node.right!=null){boolean right=pathSum(node.right,path,targetSum);if(right) return true;path.remove(path.size()-1);}return false;}