代码随想录day18

513.找树左下角的值

本题用前中后序都可以（都是先遍历左再遍历右，保证最后一定是左侧的节点），因为没有中节点的处理逻辑，用全局变量记录最大深度，只要遇到叶子结点并且当前深度比最大深度大，就更新，同时用到了回溯。

深度最大的叶子结点是最后一行。左侧的节点不一定是左孩子。

class Solution {
public:int maxDepth=0;int res;void traversal(TreeNode* node,int depth){if(node->left==NULL&&!node->right&&depth>maxDepth){maxDepth=depth;res=node->val;}if(node->left){depth++;traversal(node->left,depth);depth--;}if(node->right){depth++;traversal(node->right,depth);depth--;}}int findBottomLeftValue(TreeNode* root) {traversal(root,1);return res;}
};

迭代法：（层序遍历）

用每一层的第一个元素更新结果值res，最后返回的就是最后一层第一个元素。每次循环，队列都要一边弹出元素一边加入元素。

class Solution {
public:int findBottomLeftValue(TreeNode* root) {queue<TreeNode*> que;if(root) que.push(root);int res;while(!que.empty()){//先记录当前层的元素个数int size=que.size();for(int i=0;i<size;i++){TreeNode* node=que.front();que.pop();if(i==0) res=node->val;if(node->left) que.push(node->left);if(node->right) que.push(node->right);}}return res;}
};

112. 路径总和 

也是前中后序都可以，不存在中节点的处理逻辑。代码中有两处返回false的逻辑，第一处是单条路径不符合的话，返回false，第二处是如果所有的路径尝试后都没有返回true的话，就返回false。注意传入下层递归函数的值是已经减去节点后的值。

class Solution {
public:bool traversal(TreeNode* node,int curSum){if(!node->left&&!node->right&&curSum==0) return true;else if(!node->left&&!node->right&&curSum!=0) return false;//以上两个返回信息仅用于递归时if(node->left){curSum-=node->left->val;if(traversal(node->left,curSum)) return true;//下面的孩子节点告诉当前节点存在路径，那就继续向上返回true的信息curSum+=node->left->val;}if(node->right){curSum-=node->right->val;if(traversal(node->right,curSum)) return true;curSum+=node->right->val;}return false;}bool hasPathSum(TreeNode* root, int targetSum) {if(!root) return false;return traversal(root,targetSum-root->val);}
};

113.路径总和ii

注意终止条件有两个，符合/不符合，然后注意在进行下一层递归之前path已经记录了节点的数值，传入递归函数的数也是减去后的数。

class Solution {
public:vector<vector<int>> res;vector<int> path;void traversal(TreeNode* node,int cursum){//终止条件有两个，一个是符合条件，一个是不符合条件if(!node->left&&!node->right&&cursum==0){res.push_back(path);return;}if(!node->left&&!node->right) return;if(node->left){path.push_back(node->left->val);cursum-=node->left->val;traversal(node->left,cursum);cursum+=node->left->val;path.pop_back();}if(node->right){path.push_back(node->right->val);cursum-=node->right->val;traversal(node->right,cursum);cursum+=node->right->val;path.pop_back();}}vector<vector<int>> pathSum(TreeNode* root, int targetSum) {res.clear();path.clear();if(!root) return res;path.push_back(root->val);traversal(root,targetSum-root->val);return res;}
};

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

1、如果后序数组的元素个数为0，则返回NULL

2、如果不为空，取后序数组最后一个元素为根节点的值

3、找到后序数组最后一个元素在中序数组中的位置

4、切中序数组

5、切后序数组

6、递归构造二叉树

class Solution {
public:TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {if(postorder.size()==0) return NULL;//如果不为空，取后序数组最后一个元素为节点元素int rootval=postorder[postorder.size()-1];TreeNode* root=new TreeNode(rootval);if(postorder.size()==1) return root;//找后序数组最后一个元素在中序数组中的位置，作为切割点int idx;for(idx=0;idx<inorder.size();idx++){if(inorder[idx]==rootval) break;}//切中序数组vector<int> leftinorder(inorder.begin(),inorder.begin()+idx);vector<int> rightinorder(inorder.begin()+idx+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=buildTree(leftinorder,leftpostorder);root->right=buildTree(rightinorder,rightpostorder);return root;}
};

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

class Solution {
public:TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {if(preorder.size()==0) return NULL;int rootval=preorder[0];TreeNode* root=new TreeNode(rootval);if(preorder.size()==1) return root;int index;for(index=0;index<inorder.size();index++){if(inorder[index]==preorder[0]) break;}vector<int> leftinorder(inorder.begin(),inorder.begin()+index);vector<int> rightinorder(inorder.begin()+index+1,inorder.end());vector<int> leftpreorder(preorder.begin()+1,preorder.begin()+leftinorder.size()+1);vector<int> rightpreorder(preorder.begin()+leftinorder.size()+1,preorder.end());root->left=buildTree(leftpreorder,leftinorder);root->right=buildTree(rightpreorder,rightinorder);return root;}
};

划分左中序区间的时候边界问题出错。