day-18 代码随想录算法训练营（19）二叉树 part05

513.找树左下角的值

思路一：层序遍历，每一层判断是不是最后一层，是的话直接返回第一个;
              如何判断是不是最后一层呢，首先队列头部，其次记录左右子节点都没有的节点数是不是等于que.size()；或者直接判断队列是否为空。其实也不用判断，因为最后一次记录的队列头就是最左下角节点

class Solution {
public:int findBottomLeftValue(TreeNode* root) {queue<TreeNode*>que;que.push(root);int res=0;while(!que.empty()){int n=que.size();int mid=que.front()->val;for(int i=0;i<n;i++){TreeNode*node=que.front();que.pop();if(node->left)que.push(node->left);if(node->right)que.push(node->right);}if(que.empty())res=mid;}return res;}
};

思路二：递归，每次遍历到叶子节点时记录节点值和深度，使用数组，找到深度最深的第一个

class Solution {
public:vector<vector<int>> ans;void judge(TreeNode*root,int deepth){if(root==nullptr)return;if(root->left==nullptr && root->right==nullptr)ans.push_back({deepth,root->val});judge(root->left,deepth+1);judge(root->right,deepth+1);}int findBottomLeftValue(TreeNode* root) {judge(root,0);int  mid=0,res=0;for(int i=0;i<ans.size();i++){if(ans[i][0]>mid){mid=ans[i][0];res=i;}}return ans[res][1];}
};

思路三：递归，不使用额外空间，每次遍历到叶子节点是进行深度判断

class Solution {
public:int maxDeepth=-1;int res=0;void judge(TreeNode*root,int deepth){if(root==nullptr)return;if(root->left==nullptr && root->right==nullptr)//遍历到叶子节点时{if(deepth>maxDeepth){maxDeepth=deepth;res=root->val;}}judge(root->left,deepth+1);judge(root->right,deepth+1);}int findBottomLeftValue(TreeNode* root) {judge(root,0);return res;}
};

注意：deepth是值传递，只有父节点的改变影响子节点的值；同为子节点是相互不影响的，所以相当于回溯了。

112.路径总和

思路：递归前序遍历二叉树，在叶子节点处进行判断

class Solution {
public:bool res=false;void judge(TreeNode*root,int targetSum,int sum){if(root==nullptr)return;if(root->left==nullptr && root->right==nullptr){if(sum+root->val==targetSum)res=true;//cout<<sum;}sum+=root->val;// if(sum>targetSum)//     return;judge(root->left,targetSum,sum);judge(root->right,targetSum,sum);}bool hasPathSum(TreeNode* root, int targetSum) {judge(root,targetSum,0);return res;}
};

113.路径总和||

思路一：还是直接递归，然后在叶子节点处判断

注意：每次当前节点判断完之后需要删除路径的最后一个节点，即回溯到另一个节点

class Solution {
public:vector<vector<int>>res;vector<int>mids;void judge(TreeNode*root,int targetSum,int sum){if(root==nullptr)return;if(root->left==nullptr && root->right==nullptr){if(sum+root->val==targetSum){mids.push_back(root->val);res.push_back(mids);mids.erase(mids.end()-1);return;}}sum+=root->val;mids.push_back(root->val);judge(root->left,targetSum,sum);judge(root->right,targetSum,sum);mids.erase(mids.end()-1);}vector<vector<int>> pathSum(TreeNode* root, int targetSum) {//思路一：直接递归，在叶子节点处判断if(root==nullptr)return vector<vector<int>>();judge(root,targetSum,0);return res;}
};

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

分析：这个递归切割的想法很精妙

class Solution {
private:TreeNode*judge(vector<int>&inorder,vector<int>&postorder){if(postorder.size()==0)  return NULL;//后续遍历数组最后一个元素，就是当前二叉树的中间节点int rootValue=postorder[postorder.size()-1];TreeNode*root=new TreeNode(rootValue);//叶子节点if(postorder.size()==1) return root;//找到中序遍历的切割点int midLastIndex;for(midLastIndex=0;midLastIndex<inorder.size();midLastIndex++){if(inorder[midLastIndex]==rootValue) break;}//切割中序数组//左闭右开区间[0,midLastIndex]vector<int> leftInorder(inorder.begin(),inorder.begin()+midLastIndex);vector<int> rightInorder(inorder.begin()+midLastIndex+1,inorder.end());//删除后序数组的末尾元素postorder.resize(postorder.size()-1);//切割后序数组//依然左闭右开，注意这里使用了左中序数组大小作为切割点vector<int> leftPostorder(postorder.begin(),postorder.begin()+leftInorder.size());vector<int> rightPostorder(postorder.begin()+leftInorder.size(),postorder.end());root->left=judge(leftInorder,leftPostorder);root->right=judge(rightInorder,rightPostorder);return root;}
public:TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {if(inorder.empty() || postorder.empty()) return nullptr;return judge(inorder,postorder);}
};

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

分析：和中序和后序遍历序列构造二叉树几乎一摸一样

思路：每次构建中间节点，把前序和中序遍历序列进行分割，再递归到下一层，把分割后的序列传入下一层，最后依次把创建出来的中间节点返回给上一层连接（回溯）

class Solution {
public:TreeNode* judge(vector<int>&preorder,vector<int>&inorder){if(preorder.size()==0) return nullptr;int rootValue=preorder[0];TreeNode*root=new TreeNode(rootValue);if(preorder.size()==1)  return root;//在中序序列中找到切割点int mid;for(mid=0;mid<inorder.size();mid++){if(inorder[mid]==rootValue) break;}//对中序遍历序列进行切割vector<int>leftInorder(inorder.begin(),inorder.begin()+mid);vector<int>rightInorder(inorder.begin()+mid+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());//把切割后的序列传入下一层root->left=judge(leftPreorder,leftInorder);root->right=judge(rightPreorder,rightInorder);//把创建出来的中间节点传入上一层return root;}TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {if(preorder.empty() || inorder.empty())  return nullptr;return judge(preorder,inorder);}
};

107.二叉树的层序遍历II

思路：简单的层序遍历，加入栈然后取出

class Solution {
public:vector<vector<int>> levelOrderBottom(TreeNode* root) {//思路：层序遍历，然后把每一层的数据加入栈中，最后再从栈中取出vector<vector<int>>res;if(root==nullptr) return res;queue<TreeNode*>que;stack<vector<int>>midSt;que.push(root);while(!que.empty()){int n=que.size();vector<int>mids;for(int i=0;i<n;i++){TreeNode*cur=que.front();mids.push_back(cur->val);que.pop();if(cur->left) que.push(cur->left);if(cur->right) que.push(cur->right);}midSt.push(mids);}cout<<midSt.size();int len=midSt.size();for(int i=0;i<len;i++){res.push_back(midSt.top());midSt.pop();}return res;}
};

今日问题：43.字符串相乘

849. 到最近的人的最大距离