当前位置：首页 > news >正文

8.29 二叉树中等 113 Path Sum II 437 Path Sum III

news 2025/7/29 3:47:27

113 437 129 236 四道题可以合并起来练都是基于寻找【root to leaf】的路径做出的一些变形，主要解决思路是DFS 递归。写完递归再根据例子走一遍代码过程，以防一些小细节出问题。

e.g. 在437 中 if(currentSum == targetSum)这一步直接return true了，阻碍了后面路径的可能性[1,-2,-3,1,3,-2,null,-1]这个例子中路径[1,-2]满足条件，如果此时return true后面的路径[1,-2,1,-1]就找不到了，res就会少一个。

113 Path Sum II

在这里插入图片描述

/*** 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:vector<vector<int>> path;bool pathFind(TreeNode* node ,int currentSum,vector<int> prev,int targetSum){//找路径并记录、计算到头后判断与targetSum是否相等，如果相等就直接返回//限定底部,叶子结点if(!node->left && !node->right){currentSum += node->val;prev.push_back(node->val);if(currentSum == targetSum){path.push_back(prev);}return true;}if(node){currentSum += node->val;prev.push_back(node->val);}if(node->left)pathFind(node->left , currentSum , prev,targetSum);if(node->right)pathFind(node->right , currentSum , prev,targetSum);return false;}vector<vector<int>> pathSum(TreeNode* root, int targetSum) {//目标和 返回和targetSum相等的路径//路径用权值就可if(!root) return{};//一条条路径计算，类似于之前的129 Sum Root to Leaf Numbersvector<int> prev;pathFind(root,0,prev,targetSum);return path;}
};

437 Path Sum III

在这里插入图片描述

/*** 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:int res = 0; bool pathFind(TreeNode* node, int targetSum,long long currentSum){currentSum+=node->val;if(currentSum == targetSum){res++;}//到叶子结点但不等于targetSum直接 return falseif(!node->left && !node->right){return false;}if(node->left) {pathFind(node->left , targetSum , currentSum);}if(node->right) {pathFind(node->right , targetSum , currentSum);}return true;}int pathSum(TreeNode* root, int targetSum) {//6//不需要一定从root到leaf也可以是某个路径中的一部分，但总体还是从头到尾的//所以dfs仍旧保持，但是需要每个结点都搞一遍dfs,计数if(!root) return 0; stack<TreeNode*> stk;stk.push(root);while(!stk.empty()){TreeNode* node = stk.top();stk.pop();pathFind(node,targetSum,0);if(node->right) stk.push(node->right);if(node->left) stk.push(node->left);}return res;}
};