112.路径总和

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

叶子节点 是指没有子节点的节点。

分析：
找路径这类题使用层序遍历就不合适，而是使用深度遍历，对于二叉树，使用递归会简单一些。这道题要注意说的是叶子结点，即在判断是否和为target之前，最好先判断一些是否是叶子结点。然后只要有一个符合即可，所以要用或运算来递归左右子树。

递归法：
public boolean hasPathSum(TreeNode root, int targetSum) {
return sup(root,targetSum);
}
private boolean sup(TreeNode node,int target){
if(node==null) return false;
target-=node.val;
if(node.left==null&&node.right==null&&target==0) return true;
return sup(node.left,target)||sup(node.right,target);
}

迭代法：
用两个栈进行模拟，一个栈为正常的前序遍历，一个栈记录此时的路径和
public boolean hasPathSum(TreeNode root, int targetSum) {
if(root==null) return false;
Stack s1 = new Stack<>();
Stack s2 = new Stack<>();
s1.push(root);
s2.push(root.val);
while(!s1.isEmpty()){
int size = s1.size();
for(int i=0;i TreeNode tmp=s1.pop();
int sum=s2.pop();
if(tmp.left==null&&tmp.right==null&&sum==targetSum) return true;
if(tmp.right!=null){
s1.push(tmp.right);
s2.push(sum+tmp.right.val);
}
if(tmp.left!=null){
s1.push(tmp.left);
s2.push(sum+tmp.left.val);
}
}
}
return false;
}