【算法题】二叉树中和为某一值的路径(一)

这题让判断的是从根节点到叶子节点的所有路径中，有没有和等于 sum 的路径，我们使用 DFS 从根节点开始遍历，每到一个节点就用 sum 减去该节点的值，如果到叶子节点， sum 正好等于叶子节点的值，则存在这样的路径。

如下图所示，有两个叶子节点的值等于 sum ，说明有两条这样的路径，实际上只要存在一条即可返回 true 。

    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null)
            return false;
        // 如果到叶子节点了，并且剩余值等于叶子节点的值，返回true。
        if (root.left == null && root.right == null && sum == root.val)
            return true;
        // 分别沿着左右子节点走下去，然后顺便把当前节点的值减掉，
        // 左右子节点只要有一个返回true，说明存在这样的结果。
        return hasPathSum(root.left, sum - root.val)
                || hasPathSum(root.right, sum - root.val);
    }

public:
    bool hasPathSum(TreeNode *root, int sum) {
        if (root == nullptr)
            return false;
        // 如果到叶子节点了，并且剩余值等于叶子节点的值，返回true。
        if (root->left == nullptr && root->right == nullptr && sum == root->val)
            return true;
        // 分别沿着左右子节点走下去，然后顺便把当前节点的值减掉，
        // 左右子节点只要有一个返回true，说明存在这样的结果。
        return hasPathSum(root->left, sum - root->val)
               || hasPathSum(root->right, sum - root->val);
    }

各大厂算法面试题已经整理好了，请看这里：《算法专栏》