LeetCode112路径总和

Posted on | | Visitors:
Words count in article: 555 字 | Reading time ≈ 3 分

题目链接

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

题解一

  • 我自己写的
  • 在dfs过程中要记录当前结点与根结点之间的距离，并且回溯时也需要更新该值
  • 注意要求是叶子结点到根结点之间的距离
  • 详细思路见代码注释
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
// Problem: LeetCode 112
// URL: https://leetcode-cn.com/problems/path-sum/
// Tags: Tree Recursion DFS 回溯
// Difficulty: Easy

#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:
    bool existed = false;  // 当前是否存在叶子结点到根结点的路径和等于给定sum
    int now = 0;  // 当前结点的路径和
    int sum = -1;  // 给定的sum

    void dfs(TreeNode* root){
        // 如果当前已找到符合要求的结点，则不用再搜索
        if(existed==true)
            return ;
        // 如果是空结点，则不用搜索
        if(root==nullptr)
            return ;
        // 遍历当前结点，计算其到根结点之间的距离
        this->now += root->val;
        // 如果是叶子结点并且其与根结点的距离等于给定sum，则该结点符合条件
        if(root->left==nullptr && root->right==nullptr && this->now == this->sum){
            existed = true;
            return;
        }
        // 搜索左子树和右子树
        dfs(root->left);
        dfs(root->right);
        // 该子树已搜索完毕，需要更新当前结点与根结点之间的距离（回溯）
        this->now -= root->val;
    }

public:
    bool hasPathSum(TreeNode* root, int sum) {
        // 设置目标
        this->sum = sum;
        // 深度搜索
        dfs(root);
        // 返回搜索结果
        return this->existed;
    }
};

题解二

  • 别人的题解，用另外一种方式理解了sum，厉害 thumb up
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
// Problem: LeetCode 112
// URL: https://leetcode-cn.com/problems/path-sum/
// Tags: Tree Recursion DFS 回溯
// Difficulty: Easy

#include <iostream>
using namespace std;

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

class Solution{
public:
    bool hasPathSum(TreeNode* root, int sum) {
        if(root==nullptr)
            return false;
        if(root->left==nullptr && root->right==nullptr && root->val==sum)
            return true;
        return hasPathSum(root->left, sum-root->val) || hasPathSum(root->right, sum-root->val);
    }
};

作者：@臭咸鱼

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

欢迎讨论和交流!