问题描述

给出一棵二叉树以及一个总和 sum，判断这棵二叉树中，是否存在一条从根节点到叶子树节点的路径，其路径上所有节点的值之和正好等于这个 sum。

例如，给出下图所示的二叉树，以及 sum = 22：

      5
     / \
    4   8
   /   / \
  11  13  4
 /  \      \
7    2      1

我们应当返回 true，因为路径 5->4->11->2 之和正好为 22。

解决思路

这里看到题目跟树有关，首先应当想到使用递归。而递归分两种（可以参考leetcode 的文章）：

• 自顶向下（top-down）：如果根据参数就能知道当前节点的答案，并且通过该参数和该答案能够决定给孩子节点传什么参数，那么就用自顶向下。说白了，就是当前节点的答案可以立即给出，并且可以间接帮助其孩子节点算出答案的，我们就用 top-down。
• 自底向上（bottom-up）：如果知道孩子的答案，就能算出当前节点的答案，就用自底向上。

很显然，我们不可能立即给出当前节点的答案，给出树的根节点，我们仅仅知道根节点的值。那么就应该考虑使用 bottom-up 了。

仍然以例子中的二叉树为例：

      5
     / \
    4   8
   /   / \
  11  13  4
 /  \      \
7    2      1

当我们知道根节点的值为 5 时，如果根节点的左子树或者右子树中的任意一棵，存在一个 path sum = 22 - 5 = 17, 那么我们用这个 path sum 加上 5 就等于最终的总和 22，是不是就说明存在 path sum 了呢？也就是说，知道孩子的答案，再根据当前节点的值，就能算出当前节点的答案（是否有 path sum），于是代码就可以很自然地写出来了：

class Solution {
public:
    bool hasPathSum(TreeNode* root, int sum) {
        if (root == NULL) {
            return false;
        }
        int remain = sum - root->val;
        bool isLeaf = (root->left == NULL) && (root->right == NULL);
        bool leftAns = hasPathSum(root->left, remain);
        bool rightAns = hasPathSum(root->right, remain);
        return (leftAns || rightAns || (isLeaf && remain == 0));
    }
};

同时，这段简单的代码也达到了很高的执行效率（4ms），运行速度超过了 leetcode 中该题目下的所有 C++ 提交。