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