513.找树左下角的值
思路：首先思想要纠过来，左下角并不一定是左孩子。所以我们实际上是要找最大深度的那一行的第一个，用一个maxdepth标记来记录最深那一行的第一个即可。用迭代法也是同理。
我的代码：
class Solution {
public:
int result;
int maxdepth=INT_MIN;
void tranversal(TreeNode* cur,int depth) {
if(cur->left==NULL&&cur->right==NULL) {
if(depth>maxdepth)
{
result=cur->val;
maxdepth=depth;
}
return;
}
if(cur->left) tranversal(cur->left,depth+1);
if(cur->right) tranversal(cur->right,depth+1);
return;
}
int findBottomLeftValue(TreeNode* root) {
tranversal(root,0);
return result;
}
};
112.路径总和
思路：本题又要用到回溯，因为要传入参数count，我们传入目标值，每次调用递归传入参数count减去当前节点的值，当这个count为0且是叶子节点时，就找到了这样一条路径，但count要记得回溯。这里需要bool类型返回值，将真或假的信号一直往上传传到根节点。
我的代码：
//精简版
class Solution {
public:
bool hasPathSum(TreeNode* root, int sum) {
if (!root) return false;
if (!root->left && !root->right && sum == root->val) {
return true;
}
return hasPathSum(root->left, sum – root->val) || hasPathSum(root->right, sum – root->val);
}
};
变式题：113. 路径总和 II
思路：本题需要找到所有路径，所以递归函数不需要返回值，但是难就难在多了一个path需要去递归与回溯。
我的代码：
class Solution {
public:
vector<vector<int>> result;
vector<int> path;
void tranversal(TreeNode* cur,int count) {
if(!cur->left&&!cur->right&&count==0) {
result.push_back(path);
return;
}
if(!cur->left&&!cur->right) return ;
if(cur->left) {
path.push_back(cur->left->val);
tranversal(cur->left,count-cur->left->val);
path.pop_back();
}
if(cur->right) {
path.push_back(cur->right->val);
tranversal(cur->right,count-cur->right->val);
path.pop_back();
}
return ;
}
vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
result.clear();
path.clear();
if(root==NULL) return result;
path.push_back(root->val);
tranversal(root,targetSum-root->val);
return result;
}
};
106.从中序与后序遍历序列构造二叉树
如何利用中序与后序数组得到唯一二叉树
可以参考：如何从中序与后序数组得到唯一二叉树|代码随想录
思路：明白如何确定二叉树，之后的难点就在于分割，index很多容易晕。
一共分几步：
-
第一步：如果数组大小为零的话，说明是空节点了。
-
第二步：如果不为空，那么取后序数组最后一个元素作为节点元素。
-
第三步：找到后序数组最后一个元素在中序数组的位置，作为切割点
-
第四步：切割中序数组，切成中序左数组和中序右数组 （顺序别搞反了，一定是先切中序数组）
-
第五步：切割后序数组，切成后序左数组和后序右数组
-
第六步：递归处理左区间和右区间
用数组递归比用索引递归用的空间开销更大，效率会低一点。
我的代码：
class Solution {
private:
TreeNode* tranversal(vector<int>& inorder, int inorderBegin,int inorderEnd,int postorderBegin,int postorderEnd,vector<int>& postorder) {
if(postorderBegin==postorderEnd) return NULL;
int rootval=postorder[postorderEnd-1];
TreeNode* root= new TreeNode(rootval);
if(postorderEnd-postorderBegin==1) return root;
int delimiterIndex;
for(delimiterIndex=inorderBegin;delimiterIndex<inorderEnd;delimiterIndex++){
if(inorder[delimiterIndex]==rootval) break;
}
int leftInoderBegin=inorderBegin;
int leftInoderEnd=delimiterIndex;
int rightInorderBegin=delimiterIndex+1;
int rightInorderEnd=inorderEnd;
int leftPostorderBegin=postorderBegin;
int leftPostorderEnd=postorderBegin+delimiterIndex-inorderBegin;
int rightPostorderBegin=postorderBegin+(delimiterIndex-inorderBegin);
int rightPostorderEnd=postorderEnd-1;
root->left=tranversal(inorder,leftInoderBegin,leftInoderEnd,leftPostorderBegin,leftPostorderEnd,postorder);
root->right=tranversal(inorder,rightInorderBegin,rightInorderEnd,rightPostorderBegin,rightPostorderEnd,postorder);
return root;
}
public:
TreeNode* buildTree(vector<int>& inorder,vector<int>&postorder){
if(inorder.size()==0||postorder.size()==0) return NULL;
return tranversal(inorder,0,inorder.size(),0,postorder.size(),postorder);
}
};
同类题：106. 从中序与后序遍历序列构造二叉树
思路：这道题目只需要在上一道题目的基础上把所索引、变量名修改一下即可，但是变量很多真的很晕。
我的代码：
class Solution {
private:
TreeNode* tranversal(vector<int>& inorder, int inorderBegin,int inorderEnd,int preorderBegin,int preorderEnd,vector<int>& preorder) {
if(preorderBegin==preorderEnd) return NULL;
int rootval=preorder[preorderBegin];
TreeNode* root= new TreeNode(rootval);
if(preorderEnd-preorderBegin==1) return root;
int delimiterIndex;
for(delimiterIndex=inorderBegin;delimiterIndex<inorderEnd;delimiterIndex++){
if(inorder[delimiterIndex]==rootval) break;
}
int leftInoderBegin=inorderBegin;
int leftInoderEnd=delimiterIndex;
int rightInorderBegin=delimiterIndex+1;
int rightInorderEnd=inorderEnd;
int leftPreorderBegin=preorderBegin+1;
int leftPreorderEnd=1+preorderBegin+delimiterIndex-inorderBegin;
int rightPreorderBegin=preorderBegin+(delimiterIndex-inorderBegin)+1;
int rightPreorderEnd=preorderEnd;
root->left=tranversal(inorder,leftInoderBegin,leftInoderEnd,leftPreorderBegin,leftPreorderEnd,preorder);
root->right=tranversal(inorder,rightInorderBegin,rightInorderEnd,rightPreorderBegin,rightPreorderEnd,preorder);
return root;
}
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
if(preorder.size()==0||inorder.size()==0) return NULL;
return tranversal(inorder,0,inorder.size(),0,preorder.size(),preorder);
}
};
今日总结
105、106都是二叉树比较难的题目，需要深刻理解二叉树结构，写出来代码也需要很扎实的基础，我的基础不是那么牢固，写这两道题还是比较吃力，现在看到长一点的变量名还是会晕和反感，虽然我知道这是必要而且很有用的，还需要适应一下吧，加油！
