目录
题目一：单值二叉树
如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。
只有给定的树是单值二叉树时，才返回 true；否则返回 false。
示例 1：
输入：[1,1,1,1,1,null,1] 输出：true
示例 2：
输入：[2,2,2,5,2] 输出：false
解法一：拿根结点的值去比较
也就是将root的值传入，递归进二叉树的左右字树中，比较是否每个结点都与root的val值相等， 如果最终全部相等， 就return true，有一个不同，就return false
代码如下：
class Solution
{
public:
bool _isUnivalTree(TreeNode* root, int val)
{
//开始递归遍历二叉树的所有结点
if(root == nullptr) return true;
if(root->val != val) return false;
//继续遍历左右字树
return _isUnivalTree(root->left, val) && _isUnivalTree(root->right, val);
}
bool isUnivalTree(TreeNode* root)
{
if(root == nullptr) return true;
int val = root->val;
return _isUnivalTree(root, val);
}
};解法二：每次只比较自己的左右孩子
利用传递性的原理，每次只比较root和两个孩子的值是否相同，再继续往下比，因为如果父亲和孩子的val相同，那么父亲和孙子的val自然也相同
代码如下：
class Solution
{
public:
bool isUnivalTree(TreeNode* root)
{
if(root == nullptr) return true;
if(root->left && root->left->val != root->val) return false;
if(root->right && root->right->val != root->val) return false;
return isUnivalTree(root->left) && isUnivalTree(root->right);
}
};题目二：二叉树的最大深度
给定一个二叉树 root ，返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
示例 1：
输入：root = [3,9,20,null,null,15,7] 输出：3
示例 2：
输入：root = [1,null,2] 输出：2
求二叉树的最大深度，在递归时也就是先判断是否为空，如果不为空就进入左右字树，此时再左右字树出来return时需要 + 1，因为只有root结点不为空，才会进入，这里的 + 1 就是加的root结点
代码如下：
class Solution {
public:
int maxDepth(TreeNode* root)
{
if(root == nullptr) return 0;
int left = maxDepth(root->left) + 1;
int right = maxDepth(root->right) + 1;
return left > right ? left : right;
}
};题目三：相同的树
给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
示例 1：
输入：p = [1,2,3], q = [1,2,3] 输出：true
示例 2：
输入：p = [1,2], q = [1,null,2] 输出：false
示例 3：
输入：p = [1,2,1], q = [1,1,2] 输出：false
这道题就是比较两个二叉树是否相等，所以将问题分割为相同的子问题，每次比较当前结点是否相同
如果都为空，那就是true，如果一个为空一个不为空就是false
代码如下：
class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q)
{
//先判断是否为空
if(p == nullptr && q == nullptr) return true;
//走到这，说明p和q至少有一个为空，如果进入下面的if语句，说明不同
if(p == nullptr || q == nullptr) return false;
//接着判断val值是否相同
if(p->val != q->val) return false;
//接着进入左子树和右子树继续判断
return isSameTree(p->left, q->left)
&& isSameTree(p->right, q->right);
}
};题目四：对称二叉树
给你一个二叉树的根节点 root ， 检查它是否轴对称。
示例 1：
输入：root = [1,2,2,3,4,4,3] 输出：true
示例 2：
输入：root = [1,2,2,null,3,null,3] 输出：false
对称二叉树先判断root是否为空，如果不为空，就判断左右子树是否对称，对称就是用左子树的左孩子与右子树的右孩子比较，不要把比较的对象比较错了
class Solution {
public:
bool _isSymmetric(TreeNode* leftnode, TreeNode* rightnode)
{
if(leftnode == nullptr && rightnode == nullptr)
return true;//都为空，返回true
if(leftnode == nullptr || rightnode == nullptr)
return false;//一个为空一个不为空，返回false
if(leftnode->val != rightnode->val)
return false;//两个都不为空，但是val值不同，返回false
//继续递归左树的左和右树的右，因为是对称的
return _isSymmetric(leftnode->left, rightnode->right)
&& _isSymmetric(leftnode->right, rightnode->left);
}
bool isSymmetric(TreeNode* root)
{
if(root == nullptr) return true;
//调用_isSymmetric进行比较root的左右字树
return _isSymmetric(root->left, root->right);
}
};题目五：另一棵树的子树
给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。
二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。
示例 1：
输入：root = [3,4,5,1,2], subRoot = [4,1,2] 输出：true
示例 2：
输入：root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2] 输出：false
这道题是相同的树那道题的变形题，求一个树的子树是否包含了另一个树，也就是可以将这个树的所有子树与另一个树做比较即可，判断所有子树中是否存在另一棵树
所以下面的代码可以先引入两棵树是否相同的代码，进行复用，最终的返回值在左右子树间 || ，因为只要左右子树有一个子树包含了subRoot，就符合题意，所以选 逻辑或(||) 而不是 逻辑与(&&)
代码如下：
class Solution {
public:
//判断两个树是否相同
bool isSameTree(TreeNode* p, TreeNode* q)
{
if(p == nullptr && q == nullptr)
return true;
if(p == nullptr || q == nullptr)
return false;
if(p->val != q->val)
return false;
return isSameTree(p->left, q->left)
&& isSameTree(p->right, q->right);
}
bool isSubtree(TreeNode* root, TreeNode* subRoot)
{
if(root == nullptr) return false;
//前序遍历，每次先将root与subRoot传入，比较是否相同
if(isSameTree(root, subRoot))
return true;
//如果不同，就将root的左右子树与subRoot做比较
return isSubtree(root->left, subRoot)
|| isSubtree(root->right, subRoot);
}
};题目六：二叉树的前序遍历
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
示例 1：
输入：root = [1,null,2,3] 输出：[1,2,3]
这道题非常简单，是一个经典的前序遍历，要求就是将遍历后的结点的val值存入vector中
代码如下：
class Solution
{
public:
void preorder(TreeNode* root, vector<int>& v)
{
if(root == nullptr) return;
v.push_back(root->val);
preorder(root->left, v);
preorder(root->right, v);
}
vector<int> preorderTraversal(TreeNode* root)
{
vector<int> v;
//preorder用于进行先序遍历
preorder(root, v);
return v;
}
};类似的中序，后序就不写了，与前序相比只是交换了一下顺序
题目七：二叉树遍历
编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。 例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。
输入描述：
输入包括1行字符串，长度不超过100。
输出描述：
可能有多组测试数据，对于每组数据， 输出将输入字符串建立二叉树后中序遍历的序列，每个字符后面都有一个空格。 每个输出结果占一行。
前面做的题都是接口型，这道题是IO型，也就是要我们书写所有的代码，包括输入输出
这道题需要先创建一个二叉树的结构体，包含val和左右指针
再根据给出的先序遍历的字符串，得到一个二叉树，其中 # 表示空格
再将得到的二叉树进行中序遍历打印出来
代码如下：
#include <iostream>
#include <string>
using namespace std;
//构建一个树
struct Tree
{
char val;
Tree* left;
Tree* right;
Tree(char c):val(c), left(nullptr), right(nullptr)
{}
};
//中序遍历
void order(Tree* root)
{
if(root == nullptr) return;
order(root->left);
cout << root->val << " ";
order(root->right);
}
Tree* CreateTree(char* str, int& i)
{
if(str[i] == '#')
{
i++;
return nullptr;
}
//每次如果不是 # 就new一个结点
Tree* root = new Tree(str[i++]);
//接着进入root的左右字树
root->left = CreateTree(str, i);
root->right = CreateTree(str, i);
return root;
}
int main()
{
char s[100];
cin >> s;
int i = 0;
//根据前序的字符串获得一个二叉树
Tree* root = CreateTree(s, i);
//打印中序遍历的值
order(root);
return 0;
}题目八：根据二叉树创建字符串
给你二叉树的根节点 root ，请你采用前序遍历的方式，将二叉树转化为一个由括号和整数组成的字符串，返回构造出的字符串。
空节点使用一对空括号对 "()" 表示，转化后需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。
示例 1：
输入：root = [1,2,3,4] 输出："1(2(4))(3)" 解释：初步转化后得到 "1(2(4)())(3()())" ，但省略所有不必要的空括号对后，字符串应该是"1(2(4))(3)" 。
示例 2：
输入：root = [1,2,3,null,4] 输出："1(2()(4))(3)" 解释：和第一个示例类似，但是无法省略第一个空括号对，否则会破坏输入与输出一一映射的关系。
题目要求：一个结点的左右孩子需要在该结点右边带括号，按照示例一来说明题意：
先是1()()
1有左孩子2右孩子3，所以是：1(2)(3)
2有左孩子4右孩子为空，所以是:1(2(4)())(3)
3左右孩子都为空，所以是：1(2(4)())(3()())
省略括号后，变为了1(2(4))(3)，需要注意的是，这里的省略括号，如果右孩子存在，左孩子不存在是不能省略的，因为此时分不清是左孩子还是右孩子了，详情见示例二
根据上面的样例，可以明白有这样几种情况：
①左右都不为空，则都不省略括号
②左右都为空，都省略括号
③左不为空，右为空，可以省略右括号
④左为空，右不为空，不能省略左括号
总结就是：如果右不为空，无论左边是否为空，右边都需要加括号
如果左不为空或右不为空，则左边需要加括号
代码如下：
class Solution {
public:
string tree2str(TreeNode* root) {
//若root为空，则返回一个string的匿名对象
if(root == nullptr)
{
return string();
}
//括号省略的情况
//左右都不为空则都不省略
//左右都为空，都省略
//左不为空，右为空，省略
//左为空，右不为空，不省略
//总结就是，如果右不为空，右边需要加括号
// 如果左不为空或右不为空，左边需要加括号
string str;
//to_string将val转换为字符变量，以便可以+=
str += to_string(root->val);
if(root->left || root->right)
{
str += '(';
str += tree2str(root->left);
str += ')';
}
if(root->right)
{
str += '(';
str += tree2str(root->right);
str += ')';
}
return str;
}
};题目九：二叉树的层序遍历I
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
示例 1：
输入：root = [3,9,20,null,null,15,7] 输出：[[3],[9,20],[15,7]]
示例 2：
输入：root = [1] 输出：[[1]]
示例 3：
输入：root = [] 输出：[]
这道题二叉树的层序遍历，不是简单直接将每一层打印出来，而是将每一层都保存在一个数组中，存在vector<vector<int>>，然后打印出来
现在的思路就是定义一个变量leveSize，表示每一层的个数，首先root不为空，就将root存进队列中
循环一层中的结点时，每次都将该结点的val值尾插到一个vector中，再将该结点的左右孩子插入到队列中，循环完后将vector<int>尾插到vector<vector<int>>中，接着继续循环
代码如下：
class Solution
{
public:
vector<vector<int>> levelOrder(TreeNode* root)
{
queue<TreeNode*> q;
int levelSize = 0;
if(root)
{
levelSize = 1;
q.push(root);
}
vector<vector<int>> vv;
while(!q.empty())
{
//tmp用于存储每一层结点的val值
vector<int> tmp;
//上一层有levelSize个结点，所以循环levelSize次
for(int i = 0; i < levelSize; i++)
{
//每次取出一层的一个结点，尾插进tmp中，再pop掉
TreeNode* front = q.front();
q.pop();
tmp.push_back(front->val);
//每次都需要判断该层的这个结点有没有左右孩子，如果有就插入队列
if(front->left)
q.push(front->left);
if(front->right)
q.push(front->right);
}
//到这说明某一层的结点循环完了，需要将tmp尾插到vv了
vv.push_back(tmp);
//更新下一层的levelSize，当前队列中存的就是上一层结点的左右孩子
levelSize = q.size();
}
return vv;
}
};题目十：二叉树的层序遍历II
给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
示例 1：
输入：root = [3,9,20,null,null,15,7] 输出：[[15,7],[9,20],[3]]
示例 2：
输入：root = [1] 输出：[[1]]
示例 3：
输入：root = [] 输出：[]
解法一：层序遍历I + reverse
这道题和上道题几乎一样，区别就是这道题要求自底向上的层序遍历，那么最简单的方法就是将上一道题的代码，最终返回的vv，调用算法库中的reverse即可，就翻转过来了
代码如下：
class Solution
{
public:
vector<vector<int>> levelOrderBottom(TreeNode* root)
{
int levelSize = 0;
queue<TreeNode*> q;
if(root)
{
levelSize = 1;
q.push(root);
}
vector<vector<int>> vv;
while(!q.empty())
{
vector<int> tmp;
while(levelSize--)
{
TreeNode* front = q.front();
q.pop();
tmp.push_back(front->val);
if(front->left)
q.push(front->left);
if(front->right)
q.push(front->right);
}
vv.push_back(tmp);
levelSize = q.size();
}
//与上一题的代码一样，只是下面调用了reverse
reverse(vv.begin(), vv.end());
return vv;
}
};解法二：使用栈来进行倒着输出层序遍历
因为栈是后进先出的，所以按层的次序插入以后，出栈就是自底向上的
前面的逻辑和之前一样，只是在每一层结点遍历完之后，将vector插入栈中，最后出栈即可
代码如下：
class Solution
{
public:
vector<vector<int>> levelOrderBottom(TreeNode* root)
{
int levelSize = 0;
queue<TreeNode*> q;
if(root)
{
levelSize = 1;
q.push(root);
}
vector<vector<int>> vv;
stack<vector<int>> st;
while(!q.empty())
{
vector<int> tmp;
while(levelSize--)
{
TreeNode* front = q.front();
q.pop();
tmp.push_back(front->val);
if(front->left)
q.push(front->left);
if(front->right)
q.push(front->right);
}
st.push(tmp);
levelSize = q.size();
}
//出栈
while(!st.empty())
{
vv.push_back(st.top());
st.pop();
}
return vv;
}
};题目十一：二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
示例 1：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 输出：3 解释：节点5和节点1的最近公共祖先是节点3 。
示例 2：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 输出：5 解释：节点5和节点4的最近公共祖先是节点5 。因为根据定义最近公共祖先节点可以为节点本身。
示例 3：
输入：root = [1,2], p = 1, q = 2 输出：1
这道题需要注意的就是自己也算自己的祖先，并且p/q都在这棵树中，所以就可以不用判断p/q是否存在的这种临界问题
解法一：常规解法，判断p/q的位置
我们通过观察这道题的规则，可以发现，如果一个它是左子树的结点，一个它是右子树的结点，那么它就是最近公共祖先
如果是三叉链，可以找到两个结点的路径，转换为链表相交问题，但是此题并不是三叉链
所以我们先需要判断给出的两个结点p、q在root的左还是右，如果一个在左一个在右，就说明root就是最近公共祖先，如果都在左子树，就说明公共祖先在左子树中，反之就在右子树中
这时会有个特殊情况，如果这两个结点其中一个是另一个的孩子，那么这个结点就是最近公共祖先
代码中会写一个Find函数，用于判断某一个结点是否在某一个子树中
代码如下：
class Solution {
public:
//Find函数用于寻找x结点是否在sub子树中
bool Find(TreeNode* sub, TreeNode* x)
{
if(sub == nullptr) return false;
if(sub == x) return true;
return Find(sub->left, x)
|| Find(sub->right, x);
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)
{
//这道题不会进入这个语句，因为p/q一定在root中，所以root不可能是空
//只是为了严谨写了这个语句
if(root == nullptr)
return nullptr;
//p/q其中一个是另一个的孩子，直接返回
if(root == p || root == q)
return root;
//定义四个指针，表示p/q在root的左子树还是右子树
bool pInLeft, pInRight, qInLeft, qInRight;
//p/q结点不在root的左就在右，所以可以逻辑取反
pInLeft = Find(root->left, p);
pInRight = !pInLeft;
qInLeft = Find(root->left, q);
qInRight = !qInLeft;
//如果在root的一左一右，就返回root
if((pInLeft && qInRight) || (qInLeft && pInRight))
return root;
//如果都在root的左子树，就递归进root的左子树
else if(pInLeft && qInLeft)
{
return lowestCommonAncestor(root->left, p, q);
}
//如果都在root的右子树，就递归进root的右子树
else if(pInRight && qInRight)
{
return lowestCommonAncestor(root->right, p, q);
}
//照顾编译器
return nullptr;
}
};这道题上述解法的时间复杂度是：O(H * N)，H表示树的高度
如果说题目给了这棵树是搜索二叉树，那就不需要进行Find函数来寻找了，直接通过判断val的大小就能解决，Find的时间复杂度是O(N)
但是题目并没有给这个条件，那么还能怎么优化呢
解法二：使用栈得到路径，转化为相交问题
也就是前序遍历，分别去找p和q结点，找到后将寻找结点时的结点路径存在栈中，最终将经过的路径转化为相交问题即可
而这里的用栈去解决，也就是先进行前序遍历，先将该结点放入栈中，然后继续前序遍历，直到遍历到空为止，就说明当前放入栈中结点的左孩子为空，此时就遍历当前结点的右孩子，如果也为空，那就将当前栈顶的元素pop掉
接着以目前栈顶元素为根，直到找到p和q结点为止，此时栈中存储的就是p和q的路径，由于栈后进先出的原则，得到的就是从p和q结点到root的路径，下面演示该解法的过程：
假设要找的结点是6和4，通过前序遍历，找到了6和4结点
结点6在栈中存储的路径是：6 5 3
结点4在栈中存储的路径是：4 2 5 3
因为结点4的路径长，所以先将结点4pop掉一个，变为2 5 3
此时判断两个栈中栈顶元素是否相同，如果不同就pop，如果相同就找到了最近公共祖先
首先6和2不同，都pop掉，再比较5和5，是相同的，所以直接返回结点5即可
找路径的时间复杂度是O(N)，寻找栈中的结点的最近公共祖先，时间复杂度也是O(N)，因为并没有套在一起，所以最终时间复杂度也就是O(N)，相比于上面的那种算法的O(H * N)，得到了很大的改进
代码如下：
class Solution {
public:
bool FindPath(TreeNode* root, TreeNode* x, stack<TreeNode*>& path)
{
//如果当前结点为空，就return false
if(root == nullptr) return false;
//先将当前节点插入到栈中
path.push(root);
//如果找到了当前结点，就return true
if(root == x) return true;
//在当前结点的左子树中找，如果找到就不用去右子树中找了
if(FindPath(root->left, x, path)) return true;
//在当前结点的左子树没找到，继续到右子树中找
if(FindPath(root->right, x, path)) return true;
//如果当前结点的左右字树都没有找到，就将当前的结点pop掉，再return false
path.pop();
return false;
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)
{
//创建两个栈，分别保存p和q的路径结点
stack<TreeNode*> pPath, qPath;
//在FindPath中分别找p和q的路径
FindPath(root, p, pPath);
FindPath(root, q, qPath);
//让长的路径先走出长出的部分
while(pPath.size() != qPath.size())
{
if(pPath.size() > qPath.size())
pPath.pop();
else
qPath.pop();
}
//直到找到两个路径的交点，就是最近公共祖先
while(pPath.top() != qPath.top())
{
small.pop();
big.pop();
}
return pPath.top();
}
};题目十二：搜索二叉树与双向链表
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。如下图所示
数据范围：输入二叉树的节点数 0 ≤ n ≤ 1000，二叉树中每个节点的值 0 ≤ val ≤ 1000
要求：空间复杂度O(1)（即在原树上操作），时间复杂度O(n)
注意:
1.要求不能创建任何新的结点，只能调整树中结点指针的指向。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继
2.返回链表中的第一个节点的指针
3.函数返回的TreeNode，有左右指针，其实可以看成一个双向链表的数据结构
4.你不用输出双向链表，程序会根据你的返回值自动打印输出
输入描述：
二叉树的根节点
返回值描述：
双向链表的其中一个头节点。
这道题看题目的示意图，就是采用的中序遍历
所以首先可以解决左指针 left 的问题，采用中序遍历的思路，先找到最左边的结点，将其作为cur结点，放在题目所给的图就是下面的样子：
此时执行 cur->left = prev，接着执行 prev = cur，表示改变prev的指向
中序遍历下一个结点就是6，所以中序遍历到下一个结点的时候，cur 指向6，再将 cur->left = prev
以此类推，从而完成 left 指针的指向
而 right 指针有两种方式完成指向：
第一种，采用倒着的中序遍历，即按照 右子树 -> 根 -> 左子树 的顺序，还是按照上面的方式，定义两个指针，每次遍历到结点时确定指针的指向即可，这种比较麻烦，所以看第二种方式：
第二种，按照上面指向的逻辑，prev是cur的left，所以同样的，cur就是prev的right，所以在执行 cur->left = prev时，顺便也指定 right 指针的指向，即 prev->right = cur，这里需要注意的就是prev刚开始是空指针，不能指向，所以需要判断非空再改变指向
最后至关重要的一点：prev指针需要引用传参
因为我们代码中执行的中序遍历是递归操作，prev在一层一层返回时，会变为指向调用该层递归时的结点，而我们想要的是prev一直是cur的上一个位置，不会因为递归结束就改变，所以需要传入引用调用
代码如下：
class Solution
{
public:
// 中序遍历
void Inorder(TreeNode* cur, TreeNode*& prev)
{
if(cur == nullptr) return;
Inorder(cur->left, prev);
// 指定 left 指针
cur->left = prev;
// 如果prev不为空，指定 right 指针
if(prev) prev->right = cur;
// prev 指向 cur的位置
prev = cur;
Inorder(cur->right, prev);
}
TreeNode* Convert(TreeNode* pRootOfTree)
{
TreeNode* prev = nullptr;
Inorder(pRootOfTree, prev);
// 最终需要得到中序遍历的第一个结点，所以循环找head->left即可
TreeNode* head = pRootOfTree;
// 因为有可能传入的head为空，所以while的条件加上head
while(head && head->left)
head = head->left;
return head;
}
};题目十三：前序与中序遍历序列构造二叉树
给定两个整数数组 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]
这道题就是非常经典的给一个前序和中序遍历的顺序，构造一棵树；或者是给出一个中序和后续遍历的顺序，构造一棵树，方法是一样的
但是这种情况必须要有中序，因为前序和后序是确定根结点，而中序能够确定它的左右字树
这道题首先需要根据前序遍历的顺序，依次找到当前需要创建的节点，每次找到该节点后需要在中序遍历中找到该节点，从而得到该节点的左右子树包含的节点
假设cur就是中序遍历中找到的当前节点，此时中序遍历就会分为三部分：
[inbegin, cur - 1] cur [cur + 1, inend]
这三部分的内容，就表示cur节点的和cur节点的左右子树的节点，所以就根据这三部分，继续进行递归操作，root->left 就指向 [inbegin, cur - 1] 这个区间，root->right 就指向 [cur + 1, inend] 这个区间
退出递归的条件就是区间的左端点的下标大于右端点的下标时，就退出递归，return nullptr
代码如下：
class Solution
{
public:
//创建_buildTree函数进行递归调用
//prei是前序遍历结果的首元素下标，inbegin、inend是中序遍历结果首尾元素的下标
TreeNode* _buildTree(vector<int>& preorder, vector<int>& inorder, int& prei, int inbegin, int inend)
{
if(inbegin > inend)
return nullptr;
//每次递归通过前序遍历结果创建根结点
TreeNode* root = new TreeNode(preorder[prei++]);
int cur = inbegin;
while(cur <= inend)
{
if(inorder[cur] == root->val)
break;
else
cur++;
}
// inorder序列 分为三部分
// [inbegin, cur - 1] cur [cur + 1, inend]
root->left = _buildTree(preorder,inorder,prei,inbegin,cur-1);
root->right = _buildTree(preorder,inorder,prei,cur+1,inend);
return root;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
//前序遍历首元素下标为0
int prei = 0;
//中序遍历结果首尾元素的下标为0和inorder.size()-1
TreeNode* root = _buildTree(preorder,inorder,prei,0,inorder.size()-1);
return root;
}
};题目十四：中序与后序遍历序列构造二叉树
给定两个整数数组 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]
中序和后序构造二叉树，与前面的前序和中序构造二叉树方法相差不大，只不过前序和中序的递归顺序是，根，左子树，右子树
而后序遍历是左子树，右子树，根，所以反过来就是根，右子树，左子树，在递归时就需要先确定右子树，再确定左子树
代码如下：
class Solution
{
public:
TreeNode* _buildTree(vector<int>& inorder, vector<int>& postorder, int& posi, int inbegin, int inend)
{
if(inbegin > inend) return nullptr;
TreeNode* root = new TreeNode(postorder[posi--]);
int cur = inbegin;
while(cur <= inend)
{
if(inorder[cur] != root->val) cur++;
else break;
}
// [inbeign, cur - 1] cur [cur + 1, inend]
// 先右子树再左子树
root->right = _buildTree(inorder, postorder, posi, cur + 1, inend);
root->left = _buildTree(inorder, postorder, posi, inbegin, cur - 1);
return root;
}
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder)
{
int posi = postorder.size() - 1;
return _buildTree(inorder, postorder, posi, 0, inorder.size() - 1);
}
};题目十五：二叉树的前中后序遍历（非递归实现）
前序题目为例：
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
下面是演示前序遍历的非递归实现，也就是迭代实现
因为递归和迭代是可以互相转换的，所以我们可以将前序遍历一颗二叉树理解为：
先访问左路结点，在访问左路结点的右子树
所以就可以借助栈这个数据结构，先将当前的左路结点依次放入栈中，当左路结点寻找完后，将栈中的结点依次出栈，每次出栈都执行上述的 先访问左路结点，在访问左路结点的右子树 这个操作
所以执行方式与递归非常像，只不过是使用的while循环代替递归，在遍历每个结点时都将该节点放入vector中，最后返回即可
while循环的条件是栈不为空，或是cur不为空
栈不为空是为了保证左路结点的右子树遍历完，cur不为空是为了当前遍历的结点不为空
代码如下：
class Solution
{
public:
vector<int> preorderTraversal(TreeNode* root)
{
stack<TreeNode*> st;
vector<int> v;
TreeNode* cur = root;
while(cur || !st.empty())
{
// 左路结点
while(cur)
{
v.push_back(cur->val);
st.push(cur);
cur = cur->left;
}
// 栈中的结点依次出栈
TreeNode* top = st.top();
st.pop();
// 左路结点的右子树
cur = top->right;
}
return v;
}
};同样中序遍历就只是访问时机的区别，只需要在取出栈顶元素时再push_back进vector中即可，因为将一个结点从栈中拿出来，就表示该节点的左树已经访问完成了，按照中序遍历的思路，就该访问根节点了，所以非递归实现的中序遍历的代码如下，只在标注的地方做以改变：
class Solution
{
public:
vector<int> preorderTraversal(TreeNode* root)
{
stack<TreeNode*> st;
vector<int> v;
TreeNode* cur = root;
while(cur || !st.empty())
{
while(cur)
{
st.push(cur);
cur = cur->left;
}
TreeNode* top = st.top();
st.pop();
// 出栈后再入vector
v.push_back(cur->val);
cur = top->right;
}
return v;
}
};而后序遍历相比较前序和中序更复杂一些，因为后续的遍历顺序是：左子树，右子树，根，需要左子树和右子树都遍历完，才会访问根结点
而我们上面的逻辑，当取出栈顶元素时，表示访问完该节点的左子树，那么怎么判断该节点的右子树是否已经访问了呢
分为两种情况，第一种，右子树为空，那么此时就可以直接将该结点push_back进vector中
第二种，右子树不为空，此时就可以借助prev结点判断，如果访问栈顶结点时，上一次访问的结点是该结点的右孩子，那就说明已经将该节点的右子树遍历一遍了，此时就可以直接push_back进vector中
而如果prev不是该节点的右孩子，就循环上述的过程，即执行 cur = top->right 重复
代码如下：
class Solution
{
public:
vector<int> preorderTraversal(TreeNode* root)
{
stack<TreeNode*> st;
vector<int> v;
TreeNode* prev = nullptr;
TreeNode* cur = root;
while(cur || !st.empty())
{
while(cur)
{
st.push(cur);
cur = cur->left;
}
// 当左路结点出栈，说明左子树已经访问过了
TreeNode* top = st.top();
// 这两种情况说明左右字树都遍历完了，可以访问根结点了
if(top->right == nullptr || prev == top->right)
{
v.push_back(cur->val);
// 访问根结点时将 top 赋值给 prev
prev = top;
st.pop();
}
// 如果没有访问该节点的右子树，则访问右子树
else
{
cur = top->right;
}
}
return v;
}
};二叉树相关的题目到此结束
