513.找树左下角的值
题目链接：513.找树左下角的值
文档讲解：代码随想录
状态：层递法AC，递归法没弄清思路
思路
二叉树题目要抓住题干本质->求最后一层最左侧的元素，很显然用层递法轻松适配。
递归呢？思路：最后一层->深度最大的时候赋值；最左侧->首次深度最大的时候赋值。
深度的判断很简单，本质的判断在于第一次到达该深度的时候取值：
第一种思路：使用全局变量保存当前深度，一但有更大就更新，并取值
第二种思路：使用灵神的vector大法，各个递归函数共同维护一个vector数组，其长度起到了全局变量的作用
通过该题了解了在类中写全局变量其实本质就是普通的全局变量，不要糊涂！
题解
class Solution {
public:
int max_depth = 0;
int result ;
// void sovler(TreeNode *root,int depth)
// {
// if(root == nullptr)return ;
// if(depth>max_depth)
// {
// max_depth = depth;
// result = root->val;
// }
// sovler(root->left,depth+1);
// sovler(root->right,depth+1);
// }
//递归还可以这样写
// void sovler(TreeNode *root,int depth,vector<int> &res)
// {
// if(root == nullptr)return ;
// if(depth>res.size())
// {
// res.push_back(root->val);
// }
// sovler(root->left,depth+1,res);
// sovler(root->right,depth+1,res);
// }
int findBottomLeftValue(TreeNode* root) {
// sovler(root,1);
// return result;
queue<TreeNode*> que;
int result;
que.push(root);
while(!que.empty())
{
result = que.front()->val;
int size = que.size();
while(size--)
{
if(que.front()->left!=nullptr)que.push(que.front()->left);
if(que.front()->right!=nullptr)que.push(que.front()->right);
que.pop();
}
}
return result;
}
};
112.路径总和、113.路径总和ii
题目链接：112.路径总和 113.路径总和ii
文档讲解：代码随想录
状态：Ⅰ轻松AC，Ⅱ在语法上面出现了一些错误
思路
路径总和：简单的加和与递归问题
路径总和Ⅱ：递归还是那个递归，简单的加和变成了稍稍微复杂的字符串vector<vector<int>>处理，本题纠结的点在于，我想设置全局变量res，这样就可以不用res.push_back(vec)，而直接使用auto &遍历修改即可。
！！！关键点来了(临时对象的生命周期)：
在 C++ 中，临时对象的生命周期通常在表达式结束时结束。例如：
vector<int> getVector() {
return {1, 2, 3};
}
for (auto &i : getVector()) {
i = 10;
}
在这个例子中，getVector() 返回的是一个临时的 vector<int> 对象。for 循环中的 auto &i 绑定到这个临时对象的元素上。然而，当 for 循环结束后，这个临时对象会被销毁，因此对 i 的修改不会影响任何持久的变量。
对于本题，函数内虽然return全局变量res，但是对于返回值来说是一个临时变量，所以要遍历并且重新写入res才可！
题解
//路径总和
class Solution {
public:
bool hasPathSum(TreeNode* root, int targetSum) {
if(root == nullptr)return false;
if(root->left == nullptr && root->right == nullptr && targetSum == root->val)return true;
return hasPathSum(root->left,targetSum-root->val)||hasPathSum(root->right,targetSum-root->val);
}
};
//路径总和Ⅱ
class Solution {
public:
vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
vector<int> vec;
vector<vector<int>> res;
if(root == nullptr)return res;
if(root->left == nullptr && root->right == nullptr && targetSum == root->val)
{
vec.push_back(root->val);
res.push_back(vec);
}
for(auto &i:pathSum(root->left,targetSum-root->val))
{
i.insert(i.begin(),root->val);
res.push_back(i);
}
for(auto &i:pathSum(root->right,targetSum-root->val))
{
i.insert(i.begin(),root->val);
res.push_back(i);
}
return res;
}
};
106.从中序与后序遍历序列构造二叉树
题目链接：106.从中序与后序遍历序列构造二叉树 105.从前序与中序遍历序列构造二叉树
文档讲解：代码随想录
状态：不会，重新理清树的构造方法（也是递归）
思路
先动手搞明白如何通过中序+前/后序递归构造树：
肢解：
-
第一步： 如果数组大小为零的话，说明是空节点了。
-
第二步： 如果不为空，那么取后序数组最后一个元素作为节点元素。
-
第三步： 找到后序数组最后一个元素在中序数组的位置，作为切割点
-
第四步： 切割中序数组，切成中序左数组和中序右数组 （顺序别搞反了，一定是先切中序数组）
-
第五步： 切割后序数组，切成后序左数组和后序右数组
-
第六步： 递归处理左区间和右区间
本题知识点，当用迭代器构造vector时切记区间左闭右开，因为.end()指向数组后一个位置
题解
class Solution {
public:
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
//判断后续是否为空
//不为空取最后为中间节点
//在中序中以中间节点分割
//根据中序分割后续
//传入函数
if(postorder.size() == 0)return nullptr;
TreeNode* mid_node = new TreeNode(postorder[postorder.size()-1]);
int index = 0;
for(int i = 0;i<inorder.size();i++)
{
if(inorder[i] == mid_node->val)
{
index = i;
break;
}
}
//切割中序
vector<int> mid_left(inorder.begin(),inorder.begin()+index);
vector<int> mid_right(inorder.begin()+index+1,inorder.end());
//切割后序
vector<int> back_left(postorder.begin(),postorder.begin()+mid_left.size());
vector<int> back_right(postorder.begin()+mid_left.size(),postorder.end()-1);
mid_node->left = buildTree(mid_left, back_left);
mid_node->right = buildTree(mid_right, back_right);
return mid_node;
}
};