重大违法建设项目举报网站,网站设计网上培训学校,WordPress 5.0升级,dedecms 资源类网站模板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;}
};
