0%

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

题目描述

题目链接: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