【Leetcode】每日一题2021/10/04

• 思路
  这里可以从上向下（前序）求和，也可以从下向上（后序）求和。我准备采用递归的前序遍历。
  递归三要素
  递归函数的参数和返回值：参数是树节点，目标值，截止到当前节点的和；返回值是是否与目标值相等的bool值；
  递归的终止条件：节点为空，返回false，节点是叶子节点且满足相等，返回true；
  递归的单层逻辑：前序顺序（中左右），中来判断是否满足叶子节点及相等，左右分别继续进入下一层。
  这里也是隐含了回溯，体现就在sum的值上。

class Solution {
    public boolean pathSum(TreeNode root, int targetSum, int sum) {
        if (root == null) {
            return false;
        }
        sum += root.val;    // 中
        boolean left = false;
        boolean right = false;
        if (root.left == null && root.right == null && targetSum == sum) {
            return true;
        }
        if (root.left != null) {    // 左
            left = pathSum(root.left, targetSum, sum);
        }
        if (root.right != null) {   // 右
            right = pathSum(root.right, targetSum, sum);
        }
        return left || right;
    }
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }
        return pathSum(root, targetSum, 0);
    }
}