长春火车站出站要求,濮阳建站推广哪家好,wordpress关联博客,山东饰品行业网站制作113. 路径总和 II 文章目录 [113. 路径总和 II](https://leetcode.cn/problems/path-sum-ii/)一、题目二、题解方法一#xff1a;递归另一种递归版本方法二#xff1a;迭代 一、题目
给你二叉树的根节点 root 和一个整数目标和 targetSum #xff0c;找出所有 从根节点到叶…113. 路径总和 II 文章目录 [113. 路径总和 II](https://leetcode.cn/problems/path-sum-ii/)一、题目二、题解方法一递归另一种递归版本方法二迭代 一、题目
给你二叉树的根节点 root 和一个整数目标和 targetSum 找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
叶子节点 是指没有子节点的节点。
示例 1 输入root [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum 22
输出[[5,4,11,2],[5,8,4,5]]示例 2 输入root [1,2,3], targetSum 5
输出[]示例 3
输入root [1,2], targetSum 0
输出[]提示
树中节点总数在范围 [0, 5000] 内-1000 Node.val 1000-1000 targetSum 1000
二、题解
方法一递归
算法思路 我们需要遍历二叉树中所有从根节点到叶子节点的路径以找出满足路径和等于目标和的路径。这提示我们可以使用深度优先搜索DFS来遍历树的所有可能路径。 我们可以在递归过程中维护一个当前路径的和 count从根节点开始每到一个节点我们将该节点的值在count 上进行减法处理。 如果当前节点是叶子节点即没有左右子节点我们检查 count 是否等于0。如果是我们将当前路径添加到结果中。 在递归过程中我们需要传递当前路径 path结果数组 result当前路径的和 count以及当前节点 root。
具体实现
class Solution {
public:void findPath(TreeNode *root, vectorvectorintresult, vectorint path, int count){if(root nullptr) return;path.push_back(root-val);count - root-val;if(count 0 !root-left !root-right){result.push_back(path);}if(root-left){findPath(root-left, result, path, count);}if(root-right){findPath(root-right, result, path, count);}path.pop_back(); // 回溯移除当前节点尝试其他路径}vectorvectorint pathSum(TreeNode* root, int targetSum) {vectorvectorint result;vectorint path;if(root nullptr) return result;findPath(root, result, path, targetSum);return result;}
};算法分析 时间复杂度遍历整个二叉树每个节点只访问一次所以时间复杂度为 O(N)其中 N 是树中的节点数。 空间复杂度在递归过程中我们使用了 path 数组来存储当前路径最坏情况下路径长度达到树的深度所以空间复杂度为 O(H)其中 H 是树的高度。在结果数组中我们存储了满足条件的路径最坏情况下可能会有 O(N) 个路径所以结果数组的空间复杂度也是 O(N)。
另一种递归版本
因为cpp的特性通过去掉 vectorint 中的引用符号我可以在每个递归层次中都创建了一个新的 path 向量这样可以确保在不同的递归路径之间不会共享相同的 path 对象相当于进行了回溯。
/*** 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) {}* };*/
class Solution {
public:void findPath(TreeNode *root, vectorvectorintresult, vectorint path, int count){if(root nullptr) return;path.push_back(root-val);count - root-val;if(count 0 !root-left !root-right){result.push_back(path);}if(root-left){findPath(root-left, result, path, count);}if(root-right){findPath(root-right, result, path, count);}}vectorvectorint pathSum(TreeNode* root, int targetSum) {vectorvectorint result;vectorint path;if(root nullptr) return result;int count targetSum;findPath(root, result, path, count);return result;}
};方法二迭代
算法思路
我们使用中序遍历来遍历树的节点同时维护两个栈St 用于保存遍历节点的信息pathSt 用于保存当前路径的节点值。初始时我们将根节点 root 和对应的路径值 root-val 入栈表示从根节点开始的路径。在每一次循环中我们从 St 栈中取出一个节点同时从 pathSt 中取出与该节点对应的路径。我们检查该节点是否为叶子节点如果是叶子节点并且路径值等于 targetSum则将该路径保存到 result 中。如果不是叶子节点我们将其左子节点和右子节点如果存在的话入栈并更新路径值。重复以上步骤直至 St 栈为空。
具体实现
class Solution {
public:vectorvectorint pathSum(TreeNode* root, int targetSum) {vectorvectorint result; // 用于存储符合条件的路径stackpairTreeNode*, int St; // 用于深度优先搜索的栈同时保存节点和路径和stackvectorint pathSt; // 用于保存路径的栈if (root nullptr) return result; // 处理根节点为空的情况// 初始化将根节点和路径和入栈St.push(pairTreeNode*, int(root, root-val));vectorint temp;temp.push_back(root-val);pathSt.push(temp);while (!St.empty()) {pairTreeNode*, int node St.top(); St.pop(); // 弹出栈顶节点vectorint pathT pathSt.top(); pathSt.pop(); // 弹出栈顶路径// 如果是叶子节点且路径和等于targetSum将路径保存到result中if (!node.first-left !node.first-right node.second targetSum) {result.push_back(pathT);}// 将右子节点入栈更新路径和并将路径入栈if (node.first-right) {St.push(pairTreeNode*, int(node.first-right, node.second node.first-right-val));vectorint newPathT pathT;newPathT.push_back(node.first-right-val);pathSt.push(newPathT);}// 将左子节点入栈更新路径和并将路径入栈if (node.first-left) {St.push(pairTreeNode*, int(node.first-left, node.second node.first-left-val));vectorint newPathT pathT;newPathT.push_back(node.first-left-val);pathSt.push(newPathT);}}return result; // 返回所有满足条件的路径}
};
算法分析
时间复杂度每个节点最多访问一次所以时间复杂度为 O(N)其中 N 是树的节点数。空间复杂度栈的最大空间取决于树的高度所以空间复杂度为 O(H)其中 H 是树的高度。
简化版本
class Solution {
public:vectorvectorint pathSum(TreeNode* root, int targetSum) {vectorvectorint result;vectorint path;stackTreeNode* TreeSt;stackvectorint pathSt;if(root nullptr) return result;// 初始化TreeSt.push(root);vectorint temp;temp.push_back(root-val);pathSt.push(temp);while(!TreeSt.empty()){TreeNode *node TreeSt.top();TreeSt.pop();vectorint pathT pathSt.top();pathSt.pop();if(!node-left !node-right accumulate(pathT.begin(), pathT.end(), 0) targetSum) { //这里直接计算路径上的总和result.push_back(pathT);}if(node-right){TreeSt.push(node-right);vectorint newPathT pathT; newPathT.push_back(node-right-val);pathSt.push(newPathT);}if(node-left){TreeSt.push(node-left);vectorint newPathT pathT; newPathT.push_back(node-left-val);pathSt.push(newPathT);}}return result;}
};
