二叉树 路径总和112

需求

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

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

示例：1

二叉树
输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true
解释：等于目标和的根节点到叶节点路径如上图所示。

示例：2

二叉树

输入：root = [], targetSum = 0
输出：false
解释：由于树是空的，所以不存在根节点到叶子节点的路径。

思路

递归法
根据遍历顺序进行递归取值用target去减，如果便利完结果不符合。回溯回到上一层继续遍历，知道遍历完整棵树。
层序法
一层一层进行遍历，将下层note与value相加的和放入队列继续遍历，直到value相加等于target或者整个树遍历完成。

/**
* 112. 路径总和
*/
public class HasPathSum112 {


   // 递归处理子节点元素的值
   public static boolean hasPathSum(TreeNode root, int targetSum) {
       if (root == null) return false;// 处理root=[] target=0;
       targetSum -= root.val;
       return hasPathSumNextValue(root, targetSum);
   }

   /**
    * 递归方式
    *
    * @param root
    * @param targetSum
    * @return
    */
   public static boolean hasPathSumNextValue(TreeNode root, int targetSum) {
       if (root.left == null && root.right == null && targetSum == 0) return true;
       if (root.left == null && root.right == null && targetSum != 0) return false;
//        if (root.left == null && root.right == null ) return targetSum == 0;

       if (root.left != null) {
           targetSum -= root.left.val;// 减掉当前值，0的时候代表和与target相等
           if (hasPathSumNextValue(root.left, targetSum) == true) return true;
           targetSum += root.left.val;// 回溯，计算完恢复值继续处理其他子树
       }

       if (root.right != null) {
           targetSum -= root.right.val;
           if (hasPathSumNextValue(root.right, targetSum) == true) return true;
           targetSum += root.right.val;
       }

       return false;
   }

   /**
    * 层序遍历（广度遍历）
    */
   public static boolean hasPathSum(TreeNode root, int targetSum) {
       if (root == null) return false;
       Stack<TreeNode> stack = new Stack<>();
       Stack<Integer> stack1 = new Stack<>();
       stack.push(root);
       stack1.push(root.val);

       while (!stack.isEmpty()) {
           int size = stack.size();
           for (int s = 0; s < size; s++) {
               TreeNode node = stack.pop();
               int sum = stack1.pop();
               // 如果该节点是叶子节点了，同时该节点的路径数值等于sum，那么就返回true
               if (node.left == null && node.right == null
                       && sum == targetSum) {
                   return true;
               }
               // 右节点，压进去一个节点的时候，将该节点的路径数值也记录下来
               if (node.left != null) {
                   stack.push(node.left);
                   stack1.push(sum + node.left.val);
               }
               // 左节点，压进去一个节点的时候，将该节点的路径数值也记录下来
               if (node.right != null) {
                   stack.push(node.right);
                   stack1.push(node.right.val);
               }
           }

       }
       return false;
   }

}