112. 路径总和

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

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

示例 1：

输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true

示例 2：

输入：root = [1,2,3], targetSum = 5
输出：false

示例 3：

输入：root = [1,2], targetSum = 0
输出：false

提示：

• 树中节点的数目在范围 [0, 5000] 内
• -1000 <= Node.val <= 1000
• -1000 <= targetSum <= 1000

1. 递归

class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }
        return traversal(root, root.val, targetSum);
    }

    public boolean traversal(TreeNode root, int curSum, int targetSum) {
        //若为叶子节点且 curSum = targetSum 则返回 true
        if (root.left == null && root.right == null && curSum == targetSum) {
            return true;
        }
        boolean leftFlag = false;
        boolean rightFlag = false;
        if (root.left != null) {
            leftFlag = traversal(root.left, curSum + root.left.val, targetSum);
        }
        if (root.right != null) {
            rightFlag = traversal(root.right, curSum + root.right.val, targetSum);
        }
        return leftFlag || rightFlag;
    }
}

2. 迭代

遍历的时候保存当前路径的 sum 值即可。

class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }
        Stack<Pair> stack = new Stack<>();
        stack.push(new Pair(root, root.val));
        while (!stack.isEmpty()) {
            Pair cur = stack.pop();
            root = cur.node;
            if (root.left == null && root.right == null && cur.pathSum == targetSum) {
                return true;
            }
            if (root.right != null) {
                stack.push(new Pair(root.right, cur.pathSum + root.right.val));
            }
            if (root.left != null) {
                stack.push(new Pair(root.left, cur.pathSum + root.left.val));
            }
        }
        return false;
    }

    public static class Pair {
        TreeNode node;
        int pathSum;
        Pair(TreeNode node, int pathSum) {
            this.node = node;
            this.pathSum = pathSum;
        }
    }
}