题目描述
题目链接: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,表示当前路径和为目标值,将当前路径推入结果中并返回
- 否则直接返回
- 对左右子树使用更新后的目标值进行搜索
- 搜索完成后将当前路径中最后一个元素推出,以免影响其他路径
代码如下:
/**
* 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