?
//递归法
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean hasPathSum(TreeNode root, int targetSum) {
if(root==null) return false;
return find(root,targetSum-root.val);
}public boolean find(TreeNode root,int targetSum){
if(root.left==null&&root.right==null&&targetSum==0) return true;
if(root.left==null&&root.right==null) return false;
if(root.left!=null){
targetSum-=root.left.val;
if(find(root.left,targetSum)) return true;
targetSum+=root.left.val;
}
if(root.right!=null){
targetSum-=root.right.val;
if(find(root.right,targetSum)) return true;
targetSum+=root.right.val;
}
return false;
}
}//迭代法
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean hasPathSum(TreeNode root, int targetSum) {
if(root==null) return false;
Stack<TreeNode> stack1=new Stack<>();
Stack<Integer> satck2=new Stack<>();
stack1.push(root);
satck2.push(root.val);
while(!stack1.isEmpty()){
int size=stack1.size();
for(int i=0;i<size;i++){
TreeNode node=stack1.pop();
int sum=satck2.pop();
if(node.left==null&&node.right==null&&sum==targetSum) return true;
if(node.right!=null){
stack1.push(node.right);
satck2.push(sum+node.right.val);
}
if(node.left!=null){
stack1.push(node.left);
satck2.push(sum+node.left.val);
}
}
}
return false;
}
}