XTAO's Tech Blog
0%

[Leetcode]113. Path Sum II(C++)

发表于 更新于 分类于 ， 评论数：
1.5k 1 分钟

题目描述

题目链接：113. Path Sum II

Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum.

例子

Input: [5,4,8,11,null,13,4,7,2,null,null,5,1], sum = 22
Output:
[
[5,4,11,2],
[5,8,4,5]
]

Note

  • A leaf is a node with no children

解题思路

用 dfs 递归搜索子节点：

  • 如果当前节点为空，直接返回，否则将其值推入当前路径中，并将目标值减去当前节点值
  • 如果当前节点为叶节点
    • 如果更新后的目标值为 0,表示当前路径和为目标值，将当前路径推入结果中并返回
    • 否则直接返回
  • 对左右子树使用更新后的目标值进行搜索
  • 搜索完成后将当前路径中最后一个元素推出，以免影响其他路径

代码如下：

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
 * right(right) {}
 * };
 */

#include <vector>

class Solution {
public:
    std::vector<std::vector<int>> pathSum(TreeNode* root, int sum) {
        std::vector<std::vector<int>> result;
        std::vector<int> path;
        search(root, sum, path, result);
        return result;
    }

private:
    void search(TreeNode* root, int target, std::vector<int>& path,
                std::vector<std::vector<int>>& result) {
        if (!root) return;
        path.push_back(root->val);
        target -= root->val;
        if (!root->left && !root->right) {
            if (target == 0) {
                result.push_back(path);
            }
        }
        search(root->left, target, path, result);
        search(root->right, target, path, result);

        path.pop_back();
    }
};
  • 时间复杂度: O(n)
  • 空间复杂度: O(h) — 递归深度

GitHub 代码同步地址： 113.PathSumIi.cpp

其他题目：
GitHub: Leetcode-C++-Solution
博客： Leetcode-Solutions

推荐文章