Path Sum II
发布时间:2020-12-14 05:07:02 所属栏目:大数据 来源:网络整理
导读:Given a binary tree and a sum,find all root-to-leaf paths where each path‘s sum equals the given sum. For example: Given the below binary tree and? sum = 22 , 5 / 4 8 / / 11 13 4 / / 7 2 5 1 return [ [5,4,11,2],[5,8,5]] // method1:递归
Given a binary tree and a sum,find all root-to-leaf paths where each path‘s sum equals the given sum. For example: 5 / 4 8 / / 11 13 4 / / 7 2 5 1 return [ [5,4,11,2],[5,8,5] ] //method1:递归版本 class Solution{ public: vector<vector<int>> pathSum(TreeNode* root,int sum){ vector<vector<int>> res; vector<int> out; helper(root,sum,out,res); return res; } void helper(TreeNode* node,int sum,vector<int>& out,vector<vector<int>>& res){ if(!node) return; out.push_back(node->val);//1 if(sum == node->val && !node->left && !node->right){ res.push_back(out); } helper(node->left,sum-node->val,out,res); helper(node->right,res); out.pop_back();//由于以上1处是先把val加到vector中,如果不符合需要跳转到上一级,此处需要弹出处理; } }; //迭代版本 //注意:11处要考虑最左节点不是叶子节点,下面还有一个右子节点的情况; //可以参看:https://www.cnblogs.com/grandyang/p/4042156.html class Solution{ public: vector<vector<int>> pathSum(TreeNode* root,int sum){ vector<vector<int>> res; vector<TreeNode*> s; TreeNode *cur = root,*pre = NULL; int val = 0; while(cur || !s.empty()){ while(cur){ s.push_back(cur); val += cur->val; cur = cur->left; } cur = cur->back(); if(!cur->left && !cur->right && val == sum){ vector<int> v; for(auto it : s){ v.push_back(it->val); } res.push_back(v); } if(cur->right && cur->right != pre) cur = cur->right;//11 else{ pre = cur; val -= cur->val; s.pop_back(); cur = NULL; } } return res; } }; (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |