LeetCode437路径总和III

题目链接

https://leetcode-cn.com/problems/path-sum-iii/

题解

  • 两个DFS,两个DFS作用不一样

  • 我写的,其它人的题解大概也是这个思路

  • 这道题是昨天那道题(点击查看)的扩展,建议先看一下昨天那道题的题解二。

    • 昨天那道题中的路径是根结点到叶子结点之间的路径
    • 今天这道题中的路径是任意结点到任意结点之间的路径,只要求是向下的(即从父结点到子结点)
  • 可以按照下面2步修改昨天那道题,即可得到今天这道题并求解

    1. Step1:求根结点到任意结点(而非叶子结点)之间的路径

      处理这一差异,只需要将昨天那道题判断语句中的叶子结点条件删除即可,即只判断路径长度是否相等,不管是不是叶子结点

    2. Step2:求任意结点(而非根结点)到任意结点之间的路径

      处理这一差异,只需基于昨天那道题的解法,再套一层递归,即不止求根结点,还要递归求解其左右子树并将路径数相加

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
27
28
29
30
31
32
33
34
35
// Problem: LeetCode 437
// URL: https://leetcode-cn.com/problems/path-sum-iii/
// Tags: Tree Recursion DFS
// Difficulty: Medium

#include <iostream>
using namespace std;

struct TreeNode{
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x):val(x),left(nullptr),right(nullptr){}
};

class Solution{
private:
// Step1:搜索当前子树中结点到根结点之间距离等于sum的路径数
int dfs(TreeNode* root, int sum){
if (root == nullptr)
return 0;
int count = 0;
if (root->val == sum)
count++;
return count + dfs(root->left, sum - root->val) + dfs(root->right, sum - root->val);
}

public:
int pathSum(TreeNode* root, int sum) {
if(root==nullptr)
return 0;
// Step2:结果为:以当前结点为根结点时的路径数+以左子结点为根结点时的路径数+以右子结点为根结点时的路径数;
return dfs(root, sum) + pathSum(root->left, sum) + pathSum(root->right, sum);
}
};

作者:@臭咸鱼

转载请注明出处:https://www.cnblogs.com/chouxianyu/

欢迎讨论和交流!