今日内容
- 找树左下角的值
- 路径总和 113.路径总和ii
- 从中序与后序遍历序列构造二叉树 105.从前序与中序遍历序列构造二叉树
详细布置
找树左下角的值
本地递归偏难，反而迭代简单属于模板题， 两种方法掌握一下
题目链接/文章讲解/视频讲解：https://programmercarl.com/0513.%E6%89%BE%E6%A0%91%E5%B7%A6%E4%B8%8B%E8%A7%92%E7%9A%84%E5%80%BC.html
Tips：这道题就是在层序遍历的模板上，加一个判断是否是最后一层最左边节点的逻辑即可。
我的题解：
class Solution {
public:
int findBottomLeftValue(TreeNode* root) {
queue<TreeNode*> que;
if(root!=NULL){
que.push(root);
}
int left = 0;
while(!que.empty()){
int size = que.size();
for(int i = 0; i<size;i++){
TreeNode* node = que.front();
que.pop();
if(node->left) que.push(node->left);
if(node->right) que.push(node->right);
if(i==0){
left = node->val;
}
}
}
return left;
}
};路径总和
本题 又一次设计要回溯的过程，而且回溯的过程隐藏的还挺深，建议先看视频来理解
- 路径总和，和 113. 路径总和ii 一起做了。 优先掌握递归法。
题目链接/文章讲解/视频讲解：https://programmercarl.com/0112.%E8%B7%AF%E5%BE%84%E6%80%BB%E5%92%8C.html
Tips：注意回溯思想应用即可（其实这道题只需要传参的时候临时加一下下一个节点的值就行，不需要进行明面上的回溯操作）。
我的题解：
class Solution {
public:
bool judge(TreeNode* node, int sum, int targetSum){
if(node->left == NULL && node->right == NULL){
if(sum == targetSum){
return true;
}
else{
return false;
}
}
bool left = false;
bool right = false;
if(node->left){
left = judge(node->left, sum + node->left->val, targetSum);
}
if(node->right){
right = judge(node->right, sum + node->right->val, targetSum);
}
if(left || right){
return true;
}
else{
return false;
}
}
bool hasPathSum(TreeNode* root, int targetSum) {
if(!root){
return false;
}
return judge(root, root->val, targetSum);
}
};从中序与后序遍历序列构造二叉树
本题算是比较难的二叉树题目了，大家先看视频来理解。
106.从中序与后序遍历序列构造二叉树，105.从前序与中序遍历序列构造二叉树 一起做，思路一样的
Tips：很关键的是对NULL值的处理
说到一层一层切割，就应该想到了递归。
来看一下一共分几步：
-
第一步：如果数组大小为零的话，说明是空节点了。
-
第二步：如果不为空，那么取后序数组最后一个元素作为节点元素。
-
第三步：找到后序数组最后一个元素在中序数组的位置，作为切割点
-
第四步：切割中序数组，切成中序左数组和中序右数组 （顺序别搞反了，一定是先切中序数组）
-
第五步：切割后序数组，切成后序左数组和后序右数组
-
第六步：递归处理左区间和右区间
后序数组的切割点怎么找？
后序数组没有明确的切割元素来进行左右切割，不像中序数组有明确的切割点，切割点左右分开就可以了。
此时有一个很重的点，就是中序数组大小一定是和后序数组的大小相同的（这是必然）。
中序数组我们都切成了左中序数组和右中序数组了，那么后序数组就可以按照左中序数组的大小来切割，切成左后序数组和右后序数组。
我的题解：
class Solution {
public:
// TreeNode* travelsal(vector<int>& inorder, vector<int>& postorder){
// }
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
//下面这一行很关键，对NULL值的处理
if (postorder.size() == 0) return NULL;
int cur = postorder[postorder.size() - 1];
int inorderPos;
for(inorderPos = 0; inorderPos<inorder.size();inorderPos++){
if(inorder[inorderPos] == cur){
break;
}
}
vector<int> inorderLeft(inorder.begin(), inorder.begin() + inorderPos);
vector<int> inorderRight(inorder.begin() + inorderPos + 1, inorder.end());
postorder.pop_back();
vector<int> postorderLeft(postorder.begin(), postorder.begin()+inorderLeft.size());
vector<int> postorderRight(postorder.begin()+inorderLeft.size(), postorder.end());
TreeNode* leftNode = buildTree(inorderLeft, postorderLeft);
TreeNode* rightNode = buildTree(inorderRight, postorderRight);
TreeNode* root = new TreeNode(cur, leftNode, rightNode);
return root;
}
};