LeetCode Hot100 | Day7 | 路径总和III

看路径总和III之前先看112. 路径总和 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    bool flag=false;
    void tra(TreeNode *t,int target)
    {
        if(t==nullptr)
            return ;
        target-=t->val;
        if(t->left==nullptr&&t->right==nullptr)
        {
            if(target==0)
                flag=true;
        }
        tra(t->left,target);
        tra(t->right,target);
    }
    bool hasPathSum(TreeNode* root, int targetSum) {
        tra(root,targetSum);
        return flag;
    }
};

flag表示最后的结果，是不是找到了路径

本层逻辑

目标值减去本层的数，之后是结果收集的判断，是否是叶子结点，是否已经是目标值，全为是就是true

1
2
3
4
5
6
7
8
	target-=t->val;
      if(t->left==nullptr&&t->right==nullptr)
      {
          if(target==0)
              flag=true;
      }
tra(t->left,target);
      tra(t->right,target);

之后继续遍历左子树和右子树

437.路径总和III

437. 路径总和 III - 力扣（LeetCode）

本题就不是从根节点到叶子节点，而是任意节点到任意节点，只要满足自顶向下即可

而我们之前用的模板其实是从根节点到叶子结点，接下来这么做

1.把判断是不是叶子节点的if去掉，那就是根节点到任意节点的路径

2.那么怎么从任意节点开始呢？

我们的backtracking是之前的从根节点到叶子节点的路径查询去掉了叶子结点的判断if，那就是根节点到任意路径。而在这道题里面就是当传入的targetSum为0的时候，backtracking就会从传入的节点开始向下搜索。那我们只需重新写一个遍历函数，把每个节点都当成根节点（即参数targetSum为0）传一遍，那每个节点都会向下搜索路径，所以tra就是遍历这课树，遍历的时候让backtracking从当前结点开始向下搜索找到合适的路径，然后记录结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    long long sum=0;
    void tra(TreeNode *t,long long targetSum)
    {
        if(t==nullptr)
            return;
        backtracking(t,targetSum);
        tra(t->left,targetSum);
        tra(t->right,targetSum);
    }
    void backtracking(TreeNode *t,long long targetSum)
    {
        if(t==nullptr)
            return;
        targetSum-=t->val;
        if(targetSum==0)
            sum++;
        backtracking(t->left,targetSum);
        backtracking(t->right,targetSum);
    }
    int pathSum(TreeNode* root, int targetSum) {
        tra(root,targetSum);
        return sum;
    }
};