兰州市七里河建设局网站,大连甘井子区教育公共服务平台,河南艾特网站建设公司,徐州网站建设 网站推广代码随想录二刷Day18
今日任务
513.找树左下角的值 112.路径总和 113.路径总和ii 106.从中序与后序遍历序列构造二叉树 105.从前序与中序遍历序列构造二叉树 语言#xff1a;C
513.找树左下角的值
链接#xff1a;https://leetcode.cn/problems/find-bottom-left-tree-va…代码随想录二刷Day18
今日任务
513.找树左下角的值 112.路径总和 113.路径总和ii 106.从中序与后序遍历序列构造二叉树 105.从前序与中序遍历序列构造二叉树 语言C
513.找树左下角的值
链接https://leetcode.cn/problems/find-bottom-left-tree-value/ 递归
class Solution {
public:int maxDepth INT_MIN; //这里要用负数避免树只有一层结构时无法更新resint res 0;void traversal(TreeNode* root, int depth){if(root NULL) return;if(root-left NULL root-right NULL){if(depth maxDepth){ //保证是最左边的元素如果是同一层元素的话不会更新maxDepth和res的值maxDepth depth;res root-val;}return;}if(root-left){traversal(root-left, depth 1);}if(root-right){traversal(root-right, depth 1);}}int findBottomLeftValue(TreeNode* root) {traversal(root, 0);return res;}
};迭代
class Solution {
public:int findBottomLeftValue(TreeNode* root) {queueTreeNode* que;que.push(root);int res 0;while(!que.empty()){int n que.size();for(int i 0; i n; i){TreeNode* cur que.front();que.pop();if(i 0){res cur-val;}if(cur-left) que.push(cur-left);if(cur-right) que.push(cur-right);}}return res;}
};112.路径总和
链接https://leetcode.cn/problems/path-sum/ 递归
class Solution {
public:int curSum 0;bool traversal(TreeNode* root, int target){if(root NULL) return false;if(root-left NULL root-right NULL target ! root-val) return false;if(root-left NULL root-right NULL target root-val) return true;bool left traversal(root-left, target - root-val);bool right traversal(root-right, target - root-val);return left || right;}bool hasPathSum(TreeNode* root, int targetSum) {if(root NULL) return false;return traversal(root, targetSum);}
};迭代
class Solution {
public:int curSum 0;bool traversal(TreeNode* root, int targetSum){stackTreeNode* st;st.push(root);while(!st.empty()){TreeNode* cur st.top();if(cur ! NULL){st.push(NULL);curSum cur-val; //中if(cur-left NULL cur-right NULL curSum targetSum) return true;if(cur-right) st.push(cur-right); //右if(cur-left) st.push(cur-left); //左}else{st.pop(); //NULLcur st.top();st.pop();curSum - cur-val;}}return false;}bool hasPathSum(TreeNode* root, int targetSum) {if(root NULL) return false;return traversal(root, targetSum);}
};113.路径总和ii
链接https://leetcode.cn/problems/path-sum-ii/ 递归
class Solution {
public:vectorvectorint res;vectorint path;void traversal(TreeNode* root, int target){if(root NULL) return;if(root-left NULL root-right NULL target ! root-val) return;if(root-left NULL root-right NULL target root-val){path.push_back(root-val);res.push_back(path);path.pop_back(); //回溯return;}if(root-left){path.push_back(root-val);traversal(root-left, target - root-val);path.pop_back();}if(root-right){path.push_back(root-val);traversal(root-right, target - root-val);path.pop_back();}}vectorvectorint pathSum(TreeNode* root, int targetSum) {if(root NULL) return res;traversal(root, targetSum);return res;}
};迭代
class Solution {
public:vectorvectorint res;vectorint path;int curSum 0;vectorvectorint pathSum(TreeNode* root, int targetSum) {if(root NULL) return res;stackTreeNode* st;st.push(root);while(!st.empty()){TreeNode* cur st.top();if(cur ! NULL){st.push(NULL);curSum cur-val;path.push_back(cur-val);if(cur-left NULL cur-right NULL curSum targetSum){res.push_back(path);}if(cur-right) st.push(cur-right);if(cur-left) st.push(cur-left);}else{st.pop();cur st.top();st.pop();curSum - cur-val;path.pop_back();}}return res;}
};106.从中序与后序遍历序列构造二叉树
链接https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/ 递归
class Solution {
public:TreeNode* traversal(vectorint inorder, vectorint postorder){if(postorder.size() 0) return NULL;int val postorder[postorder.size() - 1];TreeNode* root new TreeNode(val);if(postorder.size() 1) return root;int i;for(i 0; i inorder.size(); i){if(inorder[i] val) break;}postorder.resize(postorder.size() - 1);vectorint left_in(inorder.begin(), inorder.begin() i);vectorint left_post(postorder.begin(), postorder.begin() i);root-left traversal(left_in, left_post);vectorint right_in(inorder.begin() i 1, inorder.end());vectorint right_post(postorder.begin() i, postorder.end());root-right traversal(right_in, right_post);return root;}TreeNode* buildTree(vectorint inorder, vectorint postorder) {return traversal(inorder, postorder);}
};105.从前序与中序遍历序列构造二叉树
链接https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/ 递归
class Solution {
public:TreeNode* traversal(vectorint preorder, vectorint inorder){if(inorder.size() 0) return NULL;int val preorder[0];TreeNode* root new TreeNode(val);if(inorder.size() 1) return root;int i;for(i 0; i inorder.size(); i){if(inorder[i] val) break;}vectorint left_pre(preorder.begin() 1, preorder.begin() 1 i);vectorint left_in(inorder.begin(), inorder.begin() i);root-left traversal(left_pre, left_in);vectorint right_pre(preorder.begin() 1 i, preorder.end());vectorint right_in(inorder.begin() i 1, inorder.end());root-right traversal(right_pre, right_in);return root;}TreeNode* buildTree(vectorint preorder, vectorint inorder) {return traversal(preorder, inorder);}
};
