LeetCode437路径总和III

Posted on | | Visitors:
Words count in article: 538 字 | Reading time ≈ 2 分

题目链接

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/

欢迎讨论和交流!