公司商业网站怎么做,重庆市官网首页,网站友情链接 关键词经常改动,综合搜索引擎给你二叉树的根节点 root 和一个整数目标和 targetSum #xff0c;找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
叶子节点 是指没有子节点的节点。 示例 1#xff1a; 输入#xff1a;root [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum 22
输出找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
叶子节点 是指没有子节点的节点。 示例 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]]思路前序遍历将每一条到底的路径存到path中并验证是否符合条件将符合条件的路径放入res中最终返回res。
/*** 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:vectorvectorintres;vectorintpath;void DFS(TreeNode * root,int targetSum){path.push_back(root-val);if(root-leftnullptrroot-rightnullptr){int sum0;for(int i0;ipath.size();i){sumpath[i];}if(sumtargetSum){res.push_back(path);}}if(root-left){DFS(root-left,targetSum);path.pop_back();}if(root-right){DFS(root-right,targetSum);path.pop_back();}}vectorvectorint pathSum(TreeNode* root, int targetSum) {if(rootnullptr)return res;DFS(root,targetSum);return res;}
};
