【代码随想录二刷】Day18-二叉树-C++

代码随想录二刷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) {queue<TreeNode*> 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){stack<TreeNode*> 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:vector<vector<int>> res;vector<int> 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();}}vector<vector<int>> pathSum(TreeNode* root, int targetSum) {if(root == NULL) return res;traversal(root, targetSum);return res;}
};

迭代

class Solution {
public:vector<vector<int>> res;vector<int> path;int curSum = 0;vector<vector<int>> pathSum(TreeNode* root, int targetSum) {if(root == NULL) return res;stack<TreeNode*> 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(vector<int>& inorder, vector<int>& 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);vector<int> left_in(inorder.begin(), inorder.begin() + i);vector<int> left_post(postorder.begin(), postorder.begin() + i);root->left = traversal(left_in, left_post);vector<int> right_in(inorder.begin() + i + 1, inorder.end());vector<int> right_post(postorder.begin() + i, postorder.end());root->right = traversal(right_in, right_post);return root;}TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {return traversal(inorder, postorder);}
};

105.从前序与中序遍历序列构造二叉树

链接：https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
递归

class Solution {
public:TreeNode* traversal(vector<int>& preorder, vector<int>& 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;}vector<int> left_pre(preorder.begin() + 1, preorder.begin() + 1 + i);vector<int> left_in(inorder.begin(), inorder.begin() + i);root->left = traversal(left_pre, left_in);vector<int> right_pre(preorder.begin() + 1 + i, preorder.end());vector<int> right_in(inorder.begin() + i + 1, inorder.end());root->right = traversal(right_pre, right_in);return root;}TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {return traversal(preorder, inorder);}
};