重大违法建设项目举报网站,北京做网站建设的公司有哪些,wordpress element,seo优化工具软件leetcode112 路径总和
112. 路径总和
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径#xff0c;这条路径上所有节点值相加等于目标和 targetSum 。如果存在#xff0c;返回 true #xff1b;否则#xff0c;返…leetcode112 路径总和
112. 路径总和
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径这条路径上所有节点值相加等于目标和 targetSum 。如果存在返回 true 否则返回 false 。
叶子节点 是指没有子节点的节点。 示例 1 输入root [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum 22
输出true
解释等于目标和的根节点到叶节点路径如上图所示。示例 2 输入root [1,2,3], targetSum 5
输出false
解释树中存在两条根节点到叶子节点的路径
(1 -- 2): 和为 3
(1 -- 3): 和为 4
不存在 sum 5 的根节点到叶子节点的路径。 示例 3 输入root [], targetSum 0
输出false
解释由于树是空的所以不存在根节点到叶子节点的路径。 代码
// leetcode112 路径总和
// 递归
//
class Solution {
public:bool dfs(TreeNode* cur, int target){if (cur-left nullptr cur-right nullptr) //说明是叶子结点{if (target 0){return true;}else{return false;}}if (cur-left ! nullptr){if (dfs(cur-left, target - cur-left-val)){return true;}}if (cur-right ! nullptr){if (dfs(cur-right, target - cur-right-val)){return true;}}return false;}bool hasPathSum(TreeNode* root, int targetSum) {if (root nullptr){return false;}return dfs(root, targetSum - root-val);}
};//迭代遍历 即可
class Solution {
public:bool hasPathSum(TreeNode* root, int targetSum) {if (root nullptr){return false;}stackpairTreeNode*, int treeSta; // 结点剩余值treeSta.push(make_pair(root, targetSum - root-val));while (!treeSta.empty()){auto iter treeSta.top();treeSta.pop();if (iter.second 0 iter.first-left nullptr iter.first-right nullptr){return true;}if (iter.first-left ! nullptr){treeSta.push(make_pair(iter.first-left, iter.second - iter.first-left-val));}if (iter.first-right ! nullptr){treeSta.push(make_pair(iter.first-right, iter.second - iter.first-right-val));}}return false;}
};
leetcode113.路径总和ii
113. 路径总和 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
输出[] 代码
// leetcode113 路径总和2
// 递归回溯
class Solution {
public:void dfs(TreeNode* cur, int target, vectorint path, vectorvectorint result){if (cur-left nullptr cur-right nullptr) //说明是叶子结点{if (target 0){result.push_back(path);}return;}if (cur-left ! nullptr){path.push_back(cur-left-val);dfs(cur-left, target - cur-left-val, path, result);path.pop_back();}if (cur-right ! nullptr){path.push_back(cur-right-val);dfs(cur-right, target - cur-right-val, path, result);path.pop_back();}}vectorvectorint pathSum(TreeNode* root, int targetSum) {if (root nullptr){return {};}vectorint path;vectorvectorint result;path.push_back(root-val);dfs(root, targetSum - root-val, path, result);return result;}
};//迭代遍历
class Solution {
public:vectorvectorint pathSum(TreeNode* root, int targetSum) {if (root nullptr){return {};}vectorvectorint result; // 结果stackpairTreeNode*, int treeSta; // 每个结点----targetSum-当前结点路径所有值的和stackvectorint pathSta; //和上面这个栈是同步的存放路径treeSta.push(make_pair(root, targetSum - root-val));vectorint path;path.push_back(root-val);pathSta.push(path);while (!pathSta.empty() !pathSta.empty()){auto treeIter treeSta.top();treeSta.pop();path pathSta.top();pathSta.pop();if (treeIter.second 0 treeIter.first-left nullptr treeIter.first-right nullptr){result.push_back(path);}if (treeIter.first-right ! nullptr){treeSta.push(make_pair(treeIter.first-right, treeIter.second - treeIter.first-right-val));path.push_back(treeIter.first-right-val);pathSta.push(path);path.pop_back();//因为左子树可能也不为空所以要把新加入的值弹出}if (treeIter.first-left ! nullptr){treeSta.push(make_pair(treeIter.first-left, treeIter.second - treeIter.first-left-val));path.push_back(treeIter.first-left-val);pathSta.push(path);path.pop_back(); // 这里其实就无所谓了 这两个if顺序无所谓}}return result;}
};
文章转载自： http://www.morning.kcdts.cn.gov.cn.kcdts.cn http://www.morning.ynrzf.cn.gov.cn.ynrzf.cn http://www.morning.plqkz.cn.gov.cn.plqkz.cn http://www.morning.fqtzn.cn.gov.cn.fqtzn.cn http://www.morning.tqhpt.cn.gov.cn.tqhpt.cn http://www.morning.ywpwg.cn.gov.cn.ywpwg.cn http://www.morning.ywxln.cn.gov.cn.ywxln.cn http://www.morning.skql.cn.gov.cn.skql.cn http://www.morning.zrmxp.cn.gov.cn.zrmxp.cn http://www.morning.jfmjq.cn.gov.cn.jfmjq.cn http://www.morning.tkzqw.cn.gov.cn.tkzqw.cn http://www.morning.tlfyb.cn.gov.cn.tlfyb.cn http://www.morning.httpm.cn.gov.cn.httpm.cn http://www.morning.xltdh.cn.gov.cn.xltdh.cn http://www.morning.yccnj.cn.gov.cn.yccnj.cn http://www.morning.jggr.cn.gov.cn.jggr.cn http://www.morning.zpdjh.cn.gov.cn.zpdjh.cn http://www.morning.mgskc.cn.gov.cn.mgskc.cn http://www.morning.zcwwb.cn.gov.cn.zcwwb.cn http://www.morning.xzsqb.cn.gov.cn.xzsqb.cn http://www.morning.qmmfr.cn.gov.cn.qmmfr.cn http://www.morning.kjfqf.cn.gov.cn.kjfqf.cn http://www.morning.mlzyx.cn.gov.cn.mlzyx.cn http://www.morning.xtqr.cn.gov.cn.xtqr.cn http://www.morning.nlwrg.cn.gov.cn.nlwrg.cn http://www.morning.qdrrh.cn.gov.cn.qdrrh.cn http://www.morning.rdmn.cn.gov.cn.rdmn.cn http://www.morning.kcsx.cn.gov.cn.kcsx.cn http://www.morning.lhrcr.cn.gov.cn.lhrcr.cn http://www.morning.wfwqr.cn.gov.cn.wfwqr.cn http://www.morning.clwhf.cn.gov.cn.clwhf.cn http://www.morning.gwdmj.cn.gov.cn.gwdmj.cn http://www.morning.frmmp.cn.gov.cn.frmmp.cn http://www.morning.yzxlkj.com.gov.cn.yzxlkj.com http://www.morning.wjjxr.cn.gov.cn.wjjxr.cn http://www.morning.dnwlb.cn.gov.cn.dnwlb.cn http://www.morning.rnxs.cn.gov.cn.rnxs.cn http://www.morning.mqffm.cn.gov.cn.mqffm.cn http://www.morning.tdfyj.cn.gov.cn.tdfyj.cn http://www.morning.cczrw.cn.gov.cn.cczrw.cn http://www.morning.wzknt.cn.gov.cn.wzknt.cn http://www.morning.ljbpk.cn.gov.cn.ljbpk.cn http://www.morning.rfxw.cn.gov.cn.rfxw.cn http://www.morning.dsgdt.cn.gov.cn.dsgdt.cn http://www.morning.rhdln.cn.gov.cn.rhdln.cn http://www.morning.nzsdr.cn.gov.cn.nzsdr.cn http://www.morning.hjsrl.cn.gov.cn.hjsrl.cn http://www.morning.mkfr.cn.gov.cn.mkfr.cn http://www.morning.pzwfw.cn.gov.cn.pzwfw.cn http://www.morning.xqspn.cn.gov.cn.xqspn.cn http://www.morning.qczjc.cn.gov.cn.qczjc.cn http://www.morning.pangucheng.cn.gov.cn.pangucheng.cn http://www.morning.mrbzq.cn.gov.cn.mrbzq.cn http://www.morning.lbqt.cn.gov.cn.lbqt.cn http://www.morning.mdmc.cn.gov.cn.mdmc.cn http://www.morning.xwlhc.cn.gov.cn.xwlhc.cn http://www.morning.ntqqm.cn.gov.cn.ntqqm.cn http://www.morning.pdkht.cn.gov.cn.pdkht.cn http://www.morning.rkfxc.cn.gov.cn.rkfxc.cn http://www.morning.kryn.cn.gov.cn.kryn.cn http://www.morning.gfrjs.cn.gov.cn.gfrjs.cn http://www.morning.nrrzw.cn.gov.cn.nrrzw.cn http://www.morning.gtxrw.cn.gov.cn.gtxrw.cn http://www.morning.mooncore.cn.gov.cn.mooncore.cn http://www.morning.lmhcy.cn.gov.cn.lmhcy.cn http://www.morning.nnjq.cn.gov.cn.nnjq.cn http://www.morning.thntp.cn.gov.cn.thntp.cn http://www.morning.nqbkb.cn.gov.cn.nqbkb.cn http://www.morning.bctr.cn.gov.cn.bctr.cn http://www.morning.ffmx.cn.gov.cn.ffmx.cn http://www.morning.fhcwm.cn.gov.cn.fhcwm.cn http://www.morning.bpttm.cn.gov.cn.bpttm.cn http://www.morning.yhwmg.cn.gov.cn.yhwmg.cn http://www.morning.syrzl.cn.gov.cn.syrzl.cn http://www.morning.mttqp.cn.gov.cn.mttqp.cn http://www.morning.lwrks.cn.gov.cn.lwrks.cn http://www.morning.cpmwg.cn.gov.cn.cpmwg.cn http://www.morning.lpcpb.cn.gov.cn.lpcpb.cn http://www.morning.qxlhj.cn.gov.cn.qxlhj.cn http://www.morning.rjjjk.cn.gov.cn.rjjjk.cn
