LeetCode 437.路径总和 III

题目

难度:简单

给定一个二叉树,它的每个结点都存放着一个整数值。

找出路径和等于给定数值的路径总数。

路径不需要从根节点开始,也不需要在叶子节点结束,但是路径方向必须是向下的(只能从父节点到子节点)。

二叉树不超过1000个节点,且节点数值范围是 [-1000000,1000000] 的整数。

示例:

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1

返回 3,和等于 8 的路径有:

  1. 5 -> 3
  2. 5 -> 2 -> 1
  3. -3 -> 11

思路

遍历节点时,每到一个节点,回头看一下离自己最近的几个连续节点(包括自己),哪几个的符合要求。因为每次检查时,都包括自己当前的位置,所以不会有重复的问题。

例如:
sum=5,
遍历路径[1, 2, 3],当前位置为3,回头看发现3、2(走的过程为2,3)是一个可行解(路径);
LeetCode 437.路径总和 III-听海

继续往前走,遍历路径[1, 2, 3, 4, -4, 5],当前位置5,回头看发现55、-4、4两个可行解。
LeetCode 437.路径总和 III-听海

这样是不会有重复的,因为每次停下检查时,都一定要包含自己当前的位置去计算

代码

class Solution {
public:
    int pathSum(TreeNode* root, int sum)
    {
        vector<int> vals;
        int res = 0;

        recursive(root, sum, vals, res);

        return res;
    }

    void recursive(TreeNode* root, int sum, vector<int>& vals, int &r)
    {
        if (!root)
            return;

        vals.push_back(root->val); // 站在当前位置

        int tmp_sum = 0;
        for (int i = vals.size() - 1; i >= 0; -- i) {    // 回头看
            tmp_sum += vals[i];
            if (tmp_sum == sum) //找到一个可行解
                r++;
        }

        recursive(root->left, sum, vals, r);
        recursive(root->right, sum, vals, r);

        vals.pop_back();
    }

};
喜欢()
评论 (0)