代码随想录_二叉树_leetcode112、113

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;}stack<pair<TreeNode*, 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, vector<int>& path, vector<vector<int>>& 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();}}vector<vector<int>> pathSum(TreeNode* root, int targetSum) {if (root == nullptr){return {};}vector<int> path;vector<vector<int>> result;path.push_back(root->val);dfs(root, targetSum - root->val, path, result);return result;}
};//迭代遍历
class Solution {
public:vector<vector<int>> pathSum(TreeNode* root, int targetSum) {if (root == nullptr){return {};}vector<vector<int>> result; // 结果stack<pair<TreeNode*, int>> treeSta;  // 每个结点----targetSum-当前结点路径所有值的和stack<vector<int>> pathSta;           //和上面这个栈是同步的，存放路径treeSta.push(make_pair(root, targetSum - root->val));vector<int> 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;}
};