很痛苦，也是对自己放松的一种惩罚吧！大半夜的冻着脚在这里写算法，最难受的是还不会写！！！！
1.找树左下角的值
层序遍历比较简单，但是递归有点不太明白怎么整。因为要的是最后一行的最左边的值。
递归首先是要明白怎么获得我们想要的左下角，其实就是最底层的左边，那么可以确定的是只要先左遍历，就一定是最左边，但是怎么获得最底层然后去更新我们的左下角值便是此题的难处了，最后单层逻辑因为需要的整棵树的结构，所以我们的深度不仅仅是一条，需要不断回溯。
题目
给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。
假设二叉树中至少有一个节点。
示例 1:
输入: root = [2,1,3] 输出: 1
示例 2:
输入: [1,2,3,4,null,5,6,null,null,7] 输出: 7
递归思路
1.确定参数与返回值
其实这里就很玄妙了，也是上来我就想不到的点——定义全局变量。
这样的话我们返回值直接void就可以了，然后直接调用函数，我们的全局变量就会跟着变了。
参数的话，除了根节点，还要一个深度去跟我们的最大深度不断比较，已确定终止条件，也就是最底层。
int maxDepth = INT_MIN; // 全局变量 记录最大深度
int result; // 全局变量 最大深度最左节点的数值
void traversal(TreeNode* root, int depth)2.确定终止条件
这个就比较灵性，因为我们只要是先遍历左子树，那么最先进入递归的就一定是满足条件的左边第一个如果是叶子结点，那就完美满足了，也就可以终止了，但是！！不要忘记我们还需要最底层，那么就加入条件，如果当前深度大于最大深度，不就可以满足最底层，再在这里面去更新我们的最大深度以及值。
if (root->left == NULL && root->right == NULL) {
if (depth > maxDepth) {
maxDepth = depth; // 更新最大深度
result = root->val; // 最大深度最左面的数值
}
return;
}3.单层递归逻辑
无非就是加入左子树跟右子树，但是因为我们遍历的是整个树，要面面俱到，因此我们还要回溯确定其深度，保证一定是最大深度。
// 中
if (root->left) { // 左
depth++; // 深度加一
traversal(root->left, depth);
depth--; // 回溯，深度减一
}
if (root->right) { // 右
depth++; // 深度加一
traversal(root->right, depth);
depth--; // 回溯，深度减一
}
return;代码
递归
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int maxdepth=INT_MIN;
int result=0;
void traversal(TreeNode *node,int depth){
/*终止条件，因为是左开始，所以遇到叶子结点一定先是满足题目条件的
也就是最左边的，但是还需要判断是否是最底层，更新深度*/
if(node->left==nullptr&&node->right==nullptr){
if(depth>maxdepth){
maxdepth=depth;
result=node->val;
}
return;
}
//单层递归的条件，还要涉及到回溯
if(node->left){
depth++;
traversal(node->left,depth);
depth--;
}
if(node->right){
depth++;
traversal(node->right,depth);
depth--;
}
}
int findBottomLeftValue(TreeNode* root) {
traversal(root,0);
return result;
}
};迭代（层序）
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int findBottomLeftValue(TreeNode* root) {
queue<TreeNode*>que;
//vector<int>result;
int res=0;
if(root!=nullptr) que.push(root);
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;
}
};2.路径总和
很开心！！！第一次自己单独想出来了递归思路并且在debug一次后成功ac，其实也就是受到上一题的启发，我用一个全局数组存放每次遍历到叶子结点的路径总和，最后在bool函数里我只需要遍历数组跟目标去比较，返回即可，O(∩_∩)O哈哈~
不过我最初的bug也需要注意，就是不需要回溯，这点其实在回溯做了几次后有点陷入误区，我这个每次递归，返回上一层，其实我的path还是传进去的，并没有变化，很玄妙！
题目
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。
叶子节点 是指没有子节点的节点。
示例 1：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22 输出：true 解释：等于目标和的根节点到叶节点路径如上图所示。
示例 2：
输入：root = [1,2,3], targetSum = 5 输出：false 解释：树中存在两条根节点到叶子节点的路径： (1 --> 2): 和为 3 (1 --> 3): 和为 4 不存在 sum = 5 的根节点到叶子节点的路径。
示例 3：
输入：root = [], targetSum = 0 输出：false 解释：由于树是空的，所以不存在根节点到叶子节点的路径。
代码
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int>res;
void pathSum(TreeNode *node,int path){
if(node==nullptr) return;
path+=node->val;
if(node->left==nullptr&&node->right==nullptr){
res.push_back(path);
return;
}
if(node->left){
pathSum(node->left,path);
}
if(node->right){
pathSum(node->right,path);
}
}
bool hasPathSum(TreeNode* root, int targetSum) {
pathSum(root,0);
for(int i=0;i<res.size();i++){
if(res[i]==targetSum){
return true;
}
}
return false;
}
};3.路径总和Ⅱ
跟上题差不多，但是这次我一次就成功ac了，只不过空间复杂度有点高，我创建了好多数组。。。
不过还是有点爽，因为单独一次ac成功了！
题目
给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
叶子节点 是指没有子节点的节点。
示例 1：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22 输出：[[5,4,11,2],[5,8,4,5]]
示例 2：
输入：root = [1,2,3], targetSum = 5 输出：[]
示例 3：
输入：root = [1,2], targetSum = 0 输出：[]
代码
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int>respath;
vector<vector<int>>res;
void pathAdd(TreeNode *node,int path,vector<int>p){
if(node==nullptr) return;
path+=node->val;
p.push_back(node->val);
if(node->left==nullptr&&node->right==nullptr){
respath.push_back(path);
res.push_back(p);
}
pathAdd(node->left,path,p);
pathAdd(node->right,path,p);
}
vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
vector<int>p;
vector<vector<int>>record;
pathAdd(root,0,p);
for(int i=0;i<respath.size();i++){
if(respath[i]==targetSum){
record.push_back(res[i]);
}
}
return record;
}
};4.从中序和后序遍历构建二叉树
一开始是懵的，看了视频后，对于思路就很清晰了，但是仅仅是思路清晰了，最后的代码切割还是比较难想的，而且如果不是看了题解，相比对于思路也是一团浆糊。
不过我这里只写出了这种好理解的代码，因为反复地构造vector数组很容易造成一些错误之类的，最好还是使用索引来切割我们的中序数组与后序数组。索引版本我就直接copy的卡哥的（思路一样不过细节要更多一点）
题目
给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。
示例 1:
输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3] 输出：[3,9,20,null,null,15,7]
示例 2:
输入：inorder = [-1], postorder = [-1] 输出：[-1]
思路
这里就引用卡哥的思路了，毕竟我的思路就是看他的学的。代码随想录
首先回忆一下如何根据两个顺序构造一个唯一的二叉树，相信理论知识大家应该都清楚，就是以 后序数组的最后一个元素为切割点，先切中序数组，根据中序数组，反过来再切后序数组。一层一层切下去，每次后序数组最后一个元素就是节点元素。
如果让我们肉眼看两个序列，画一棵二叉树的话，应该分分钟都可以画出来。
流程如图：
那么代码应该怎么写呢？
说到一层一层切割，就应该想到了递归。
来看一下一共分几步：
-
第一步：如果数组大小为零的话，说明是空节点了。
-
第二步：如果不为空，那么取后序数组最后一个元素作为节点元素。
-
第三步：找到后序数组最后一个元素在中序数组的位置，作为切割点
-
第四步：切割中序数组，切成中序左数组和中序右数组 （顺序别搞反了，一定是先切中序数组）
-
第五步：切割后序数组，切成后序左数组和后序右数组
-
第六步：递归处理左区间和右区间
不难写出如下代码：（先把框架写出来）
TreeNode* traversal (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 delimiterIndex;
for (delimiterIndex = 0; delimiterIndex < inorder.size(); delimiterIndex++) {
if (inorder[delimiterIndex] == rootValue) break;
}
// 第四步：切割中序数组，得到 中序左数组和中序右数组
// 第五步：切割后序数组，得到 后序左数组和后序右数组
// 第六步
root->left = traversal(中序左数组, 后序左数组);
root->right = traversal(中序右数组, 后序右数组);
return root;
}代码
可以说是非常的详细了我的注释，一步一步也不会出错。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* traversal(vector<int>& inorder, vector<int>& postorder){
//第一步，后序数组为0，空节点
if(postorder.size()==0) return nullptr;
//第二步，后序数组最后一个元素为节点元素
int rootValue=postorder[postorder.size()-1];
TreeNode *root=new TreeNode(rootValue);
//注意这里，如果后序数组为1，返回节点元素
//if(postorder.size()==1) return root;
//第三步，寻找中序数组位置作为切割点
int index;
for(index=0;index<inorder.size();index++){
if(inorder[index]==rootValue){
break;
}
}
//第四步,切割中序数组
vector<int>leftInorder(inorder.begin(),inorder.begin()+index);
vector<int>rightInorder(inorder.begin()+index+1,inorder.end());//因为要跳过切割点所以+1
//第五步，切割后序数组
postorder.resize(postorder.size()-1);//因为要去掉切割点所以数组大小要缩小1
vector<int>leftPostorder(postorder.begin(),postorder.begin()+leftInorder.size());
vector<int>rightPostorder(postorder.begin()+leftInorder.size(),postorder.end());
//第六步，递归处理左右区间,注意要赋给左右子树
root->left=traversal(leftInorder,leftPostorder);
root->right=traversal(rightInorder,rightPostorder);
//返回
return root;
}
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
return traversal(inorder,postorder);
}
};索引法切割
class Solution {
private:
// 中序区间：[inorderBegin, inorderEnd)，后序区间[postorderBegin, postorderEnd)
TreeNode* traversal (vector<int>& inorder, int inorderBegin, int inorderEnd, vector<int>& postorder, int postorderBegin, int postorderEnd) {
if (postorderBegin == postorderEnd) return NULL;
int rootValue = postorder[postorderEnd - 1];
TreeNode* root = new TreeNode(rootValue);
if (postorderEnd - postorderBegin == 1) return root;
int delimiterIndex;
for (delimiterIndex = inorderBegin; delimiterIndex < inorderEnd; delimiterIndex++) {
if (inorder[delimiterIndex] == rootValue) break;
}
// 切割中序数组
// 左中序区间，左闭右开[leftInorderBegin, leftInorderEnd)
int leftInorderBegin = inorderBegin;
int leftInorderEnd = delimiterIndex;
// 右中序区间，左闭右开[rightInorderBegin, rightInorderEnd)
int rightInorderBegin = delimiterIndex + 1;
int rightInorderEnd = inorderEnd;
// 切割后序数组
// 左后序区间，左闭右开[leftPostorderBegin, leftPostorderEnd)
int leftPostorderBegin = postorderBegin;
int leftPostorderEnd = postorderBegin + delimiterIndex - inorderBegin; // 终止位置是 需要加上 中序区间的大小size
// 右后序区间，左闭右开[rightPostorderBegin, rightPostorderEnd)
int rightPostorderBegin = postorderBegin + (delimiterIndex - inorderBegin);
int rightPostorderEnd = postorderEnd - 1; // 排除最后一个元素，已经作为节点了
root->left = traversal(inorder, leftInorderBegin, leftInorderEnd, postorder, leftPostorderBegin, leftPostorderEnd);
root->right = traversal(inorder, rightInorderBegin, rightInorderEnd, postorder, rightPostorderBegin, rightPostorderEnd);
return root;
}
public:
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
if (inorder.size() == 0 || postorder.size() == 0) return NULL;
// 左闭右开的原则
return traversal(inorder, 0, inorder.size(), postorder, 0, postorder.size());
}
};
5.从中序和前序遍历构造二叉树
其实思路跟中序+后序差不多，但是反复用数组切割会导致数组越界，所以只能使用索引来切割数组。
题目
给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
示例 1:
输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] 输出: [3,9,20,null,null,15,7]
示例 2:
输入: preorder = [-1], inorder = [-1] 输出: [-1]
代码
简单好理解但是数组越界
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* traversal(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 index;
for(index=0;index<inorder.size();index++){
if(inorder[index]==rootValue) break;
}
vector<int>leftInorder(inorder.begin(),inorder.begin()+index);
vector<int>rightInorder(inorder.begin()+index+1,inorder.end());
preorder.resize(preorder.size()-1);
vector<int>leftPreorder(preorder.begin()+1,preorder.begin()+leftInorder.size());
vector<int>rightPreorder(preorder.begin()+leftInorder.size(),preorder.end());
root->left=traversal(leftInorder,leftPreorder);
root->right=traversal(rightInorder,rightPreorder);
return root;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
return traversal(preorder,inorder);
}
}; 索引法切割
class Solution {
private:
// 中序区间：[inorderBegin, inorderEnd)，后序区间[postorderBegin, postorderEnd)
TreeNode* traversal (vector<int>& inorder, int inorderBegin, int inorderEnd, vector<int>& postorder, int postorderBegin, int postorderEnd) {
if (postorderBegin == postorderEnd) return NULL;
int rootValue = postorder[postorderEnd - 1];
TreeNode* root = new TreeNode(rootValue);
if (postorderEnd - postorderBegin == 1) return root;
int delimiterIndex;
for (delimiterIndex = inorderBegin; delimiterIndex < inorderEnd; delimiterIndex++) {
if (inorder[delimiterIndex] == rootValue) break;
}
// 切割中序数组
// 左中序区间，左闭右开[leftInorderBegin, leftInorderEnd)
int leftInorderBegin = inorderBegin;
int leftInorderEnd = delimiterIndex;
// 右中序区间，左闭右开[rightInorderBegin, rightInorderEnd)
int rightInorderBegin = delimiterIndex + 1;
int rightInorderEnd = inorderEnd;
// 切割后序数组
// 左后序区间，左闭右开[leftPostorderBegin, leftPostorderEnd)
int leftPostorderBegin = postorderBegin;
int leftPostorderEnd = postorderBegin + delimiterIndex - inorderBegin; // 终止位置是 需要加上 中序区间的大小size
// 右后序区间，左闭右开[rightPostorderBegin, rightPostorderEnd)
int rightPostorderBegin = postorderBegin + (delimiterIndex - inorderBegin);
int rightPostorderEnd = postorderEnd - 1; // 排除最后一个元素，已经作为节点了
root->left = traversal(inorder, leftInorderBegin, leftInorderEnd, postorder, leftPostorderBegin, leftPostorderEnd);
root->right = traversal(inorder, rightInorderBegin, rightInorderEnd, postorder, rightPostorderBegin, rightPostorderEnd);
return root;
}
public:
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
if (inorder.size() == 0 || postorder.size() == 0) return NULL;
// 左闭右开的原则
return traversal(inorder, 0, inorder.size(), postorder, 0, postorder.size());
}
};