代码随想录day16二叉树4

513.找树左下角的值

题目链接
文章讲解

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int findBottomLeftValue(TreeNode* root) {queue<TreeNode*> q;if(root) q.push(root);vector<int> res;int ans=0;while(!q.empty()){int k=q.size();bool flag=false;while(k--){TreeNode* node=q.front();q.pop();//每次存最左边的值if(!flag) {ans=node->val;flag=true;}if(node->left) q.push(node->left);if(node->right) q.push(node->right);}}return ans;}
};

112. 路径总和

题目链接
文章讲解

参照昨天的二叉树的所有路径

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:void all(TreeNode* cur,vector<int>& path,int targetSum,bool& flag){path.push_back(cur->val);if(!cur->left&&!cur->right){int ans=0;for(int i=0;i<path.size();i++){ans+=path[i];}if(ans==targetSum) flag=true;}if(cur->left){all(cur->left,path,targetSum,flag);path.pop_back();}if(cur->right){all(cur->right,path,targetSum,flag);path.pop_back();}}bool hasPathSum(TreeNode* root, int targetSum) {vector<int> path;bool flag=false;if(root==NULL) return false;all(root,path,targetSum,flag);return flag;}
};

113. 路径总和 II

题目链接
文章讲解

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:void all(TreeNode* cur,vector<int>& path,int targetSum,vector<vector<int>>& res){path.push_back(cur->val);if(!cur->left&&!cur->right){int ans=0;for(int i=0;i<path.size();i++){ans+=path[i];}if(ans==targetSum) {res.push_back(path);}}if(cur->left){all(cur->left,path,targetSum,res);path.pop_back();}if(cur->right){all(cur->right,path,targetSum,res);path.pop_back();}}vector<vector<int>> pathSum(TreeNode* root, int targetSum) {vector<int> path;vector<vector<int>> res;if(root==NULL) return res;all(root,path,targetSum,res);return res;}
};

106.从中序与后序遍历序列构造二叉树

题目链接
文章讲解

第一步：如果数组大小为零的话，说明是空节点了。

第二步：如果不为空，那么取后序数组最后一个元素作为节点元素。

第三步：找到后序数组最后一个元素在中序数组的位置，作为切割点

第四步：切割中序数组，切成中序左数组和中序右数组 （顺序别搞反了，一定是先切中序数组）

第五步：切割后序数组，切成后序左数组和后序右数组

第六步：递归处理左区间和右区间

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:TreeNode* solve(vector<int>& inorder, vector<int>& postorder){if(postorder.size()==0) return NULL;int fenge=postorder[postorder.size()-1];TreeNode* node=new TreeNode(fenge);if(postorder.size()==1) return node;int k=0;for(int i=0;i<inorder.size();i++){if(inorder[i]==fenge){k=i;break;}}vector<int> leftinorder(inorder.begin(),inorder.begin()+k);//特别注意这里要加1vector<int> rightinorder(inorder.begin()+k+1,inorder.end());postorder.pop_back();vector<int> leftpostorder(postorder.begin(),postorder.begin()+leftinorder.size());vector<int> rightpostorder(postorder.begin()+leftinorder.size(),postorder.end());node->left=solve(leftinorder,leftpostorder);node->right=solve(rightinorder,rightpostorder);return node;}TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {if(inorder.size()==0||postorder.size()==0) return NULL;return solve(inorder,postorder);}
};

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

题目链接
文章讲解

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:TreeNode* solve(vector<int>& preorder, vector<int>& inorder){if(preorder.size()==0)  return NULL;int fenge=preorder[0];TreeNode* node=new TreeNode(fenge);if(preorder.size()==1) return node;int k;for(int i=0;i<inorder.size();i++){if(inorder[i]==fenge){k=i;break;}}vector<int> leftinorder(inorder.begin(),inorder.begin()+k);vector<int> rightinorder(inorder.begin()+k+1,inorder.end());preorder.erase(preorder.begin());vector<int> leftpreorder(preorder.begin(),preorder.begin()+leftinorder.size());vector<int> rightpreorder(preorder.begin()+leftinorder.size(),preorder.end());node->left=solve(leftpreorder,leftinorder);node->right=solve(rightpreorder,rightinorder);return node;}TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {if(preorder.size()==0||inorder.size()==0) return NULL;return solve(preorder,inorder);}
};