二叉树---路径总和

题目：

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

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

思路一：递归法。

第一步：确定参数与返回值。参数为树节点，一个int类型的计数器，返回值为bool类型

第二步：确定终止条件。用递减，让计数器count初始为目标和，然后每次减去遍历路径节点上的数值。如果最后count == 0，同时到了叶子节点的话，说明找到了目标和。如果遍历到了叶子节点，count不为0，就是没找到。

第三步：确定单层递归逻辑。因为终止条件是判断叶子节点，所以递归的过程中就不要让空节点进入递归了。递归函数是有返回值的，如果递归函数返回true，说明找到了合适的路径，应该立刻返回。

代码：

    public boolean hasPathSum(TreeNode root, int targetSum) {
        if(root==null) return false;
        return traversal(root,targetSum-root.val);
    }
    public boolean traversal(TreeNode node,int count){
        if(node.left==null&&node.right==null&&count==0) return true;//叶子节点，且路径和为目标值
        if(node.left==null&&node.right==null) return false;//叶子节点，路径和不为目标值，回溯判断其他路径
        if(node.left!=null){
            count-=node.left.val;
            if(traversal(node.left,count)) return true;
            count+=node.left.val;//回溯
        }
        if(node.right!=null){
            count-=node.right.val;
            if(traversal(node.right,count)) return true;
            count+=node.right.val;//回溯
        }
        return false;
    }

思路二：迭代法。使用前序遍历，一个栈存放前序遍历的节点，一个栈存放根节点到该节点的值。

代码：

 public boolean hasPathSum(TreeNode root, int targetSum) {
        if(root==null) return false;
        Stack<TreeNode> stack1=new Stack<>();//前序遍历栈
        Stack<Integer> stack2=new Stack<>();//记录根节点到每个节点的值
        stack1.push(root);
        stack2.push(root.val);
        while(!stack1.isEmpty()){
            int len=stack1.size();
            for(int i=0;i<len;i++){
                TreeNode node=stack1.pop();
                int sum=stack2.pop();
                if(node.left==null&&node.right==null&&sum==targetSum) return true;
                if(node.right!=null){
                    stack1.push(node.right);
                    stack2.push(sum+node.right.val);
                }
                if(node.left!=null){
                    stack1.push(node.left);
                    stack2.push(sum+node.left.val);
                }
            }
        }
        return false;
    }