逆序思维

路径总和

原做法, 用了sum保存根节点到当前节点的值

class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        return recur(root, targetSum, 0);
    }

    public boolean recur(TreeNode root, int targetSum, int sum) {
        if(root == null)
            return false;
        sum += root.val;
        if(root.left == null && root.right == null && sum == targetSum)
            return true;
        return recur(root.left, targetSum, sum) || recur(root.right, targetSum, sum);
    }
}

假定从根节点到当前节点的值之和为 val，我们可以将这个大问题转化为一个小问题：是否存在从当前节点的子节点到叶子的路径，满足其路径和为 sum - val

class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) {
            return false;
        }
        if (root.left == null && root.right == null) {
            return sum == root.val;
        }
        return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
    }
}

最后一个单词的长度

一开始用双指针, 由头开始统计, 其实可以反向遍历