摘要：
- 二叉搜索树与双向链表；
- 从前序与中序遍历序列构造二叉树，从中序与后序遍历序列构造二叉树；
- 二叉树的前序遍历二叉树(非递归)，二叉树的中序遍历(非递归)，二叉树的后序遍历(非递归)
前言：本文提供部分比较典型的适合练习二叉树进阶内容的OJ试题的分析和代码。如有错误，烦请指正。
（有几道题解法很相似，思路相同的部分会省略分析，如有某一题不解可以参看相似题的讲解）
目录
1. 二叉搜索树与双向链表（递归）
题源：二叉搜索树与双向链表_牛客题霸_牛客网 (nowcoder.com)
描述
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。如下图所示：
数据范围：输入二叉树的节点数 0≤𝑛≤10000≤n≤1000，二叉树中每个节点的值 0≤𝑣𝑎𝑙≤10000≤val≤1000
要求：空间复杂度𝑂(1)（即在原树上操作），时间复杂度 𝑂(𝑛)注意:
1.要求不能创建任何新的结点，只能调整树中结点指针的指向。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继
2.返回链表中的第一个节点的指针
3.函数返回的TreeNode，有左右指针，其实可以看成一个双向链表的数据结构4.你不用输出双向链表，程序会根据你的返回值自动打印输出
题解
根据题目所给的示例，首先，我们需要中序遍历这棵树，按中序遍历的顺序取到每个结点，依次进行处理。
如上图对题例的分步分析，pCur(当前结点指针) 的变化：4 → 6 → 8 → 10 → 12 → 14 → 16，显然 pCur 是一个中序遍历的变化过程，对于 pCur 可以通过递归来控制。另外，pPrev 用于记录 pCur “前一个结点的指针”，紧随 pCur 变化而变化。
最后，转换(Convert)之后的树的根节点变更为原树的最左结点。
代码
class Solution {
public:
void _Convert(TreeNode* pCur,TreeNode*& pPrev)
{
if(pCur == nullptr)
return;
_Convert(pCur->left, pPrev);
pCur->left = pPrev;
if(pPrev)
pPrev->right = pCur;
pPrev = pCur;//pPrev是随着pCur改变而改变的，并且是持续变化的，与递归到哪一层无关，因此pPrev要用传引用传参
_Convert(pCur->right, pPrev);
}
TreeNode* Convert(TreeNode* pRootOfTree) {
if(pRootOfTree == nullptr)
return nullptr;
TreeNode* pPrev;
_Convert(pRootOfTree, pPrev);
TreeNode* pCur = pRootOfTree;
while(pCur->left)
{
pCur = pCur->left;
}
return pCur;
}
};2. 从前序与中序遍历序列构造二叉树（递归）
题源：105. 从前序与中序遍历序列构造二叉树 - 力扣（LeetCode）
给定两个整数数组
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]提示:
1 <= preorder.length <= 3000inorder.length == preorder.length-3000 <= preorder[i], inorder[i] <= 3000preorder和inorder均 无重复 元素inorder均出现在preorderpreorder保证 为二叉树的前序遍历序列inorder保证 为二叉树的中序遍历序列
题解
preorder（前序）：根 左子树 右子树
inorder（中序）：左子树 根 右子树
由此可见，前序遍历序列确定根，中序遍历序列划分左子树和右子树。
如图所示，通过前序遍历序列确定根，再去中序遍历中找到根（定义这个根的下标为 rooti），然后向下递归：
左子树由中序遍历序列中下标为 [ 0 , rooti ) 的组成；
右子树由中序遍历序列中下标为 [ rooti , inorder.size() ) 的组成。
而左/右子树序列 [ 0 , rooti ) / [ rooti , inorder.size() )又可以看作一个新的递归子问题。
另外，每当成功创建一个新结点之后，preorder 也依次往后遍历。（这里的区间采用了左闭右开，具体可视情况而定）
ps.题目保证了，preorder 和 inorder 分别为前序遍历序列和后序遍历序列，因此 inorder 遍历完相应的 preorder 也一定遍历完了。因此在递归的过程中不需要判断 preorder 是否还剩未被遍历的元素。
代码
class Solution {
public:
TreeNode* _buildTree(size_t begini, size_t endi,
const vector<int>& preorder, size_t& pre_i,
const vector<int>& inorder)
{
if (begini >= endi)
{
return nullptr;
}
for (size_t rooti = begini; rooti < endi; ++rooti)
{
if (preorder[pre_i] == inorder[rooti])
{
TreeNode* root = new TreeNode(preorder[pre_i++]);
//每成功创建一个结点就preorder的序列就往后++
//[begini,rooti) rooti [rooti+1,endi)
root->left = _buildTree(begini, rooti, preorder, pre_i, inorder);
root->right = _buildTree(rooti + 1, endi, preorder, pre_i, inorder);
return root;
}
}
return nullptr;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder)
{
size_t pre_i = 0;
return _buildTree(0, inorder.size(), preorder, pre_i, inorder);
}
};3. 从中序与后序遍历序列构造二叉树（递归）
题源：106. 从中序与后序遍历序列构造二叉树 - 力扣（LeetCode）
给定两个整数数组
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]提示:
1 <= inorder.length <= 3000postorder.length == inorder.length-3000 <= inorder[i], postorder[i] <= 3000inorder和postorder都由 不同 的值组成postorder中每一个值都在inorder中inorder保证是树的中序遍历postorder保证是树的后序遍历
题解
类似与上一题。
postorder（后序）：左子树 右子树 根
inorder（中序）：左子树 根 右子树
不同于上一题的在于，我们需要倒序遍历后序遍历序列来确定根。另外，先构建右子树，再构建左子树。这里不多作分析。
代码
class Solution {
public:
TreeNode* _buidTree(const vector<int>& inorder, const vector<int>& postorder
,size_t begini,size_t endi
,size_t& posti)
{
if(begini>=endi)
return nullptr;
size_t post_backi = postorder.size()-1;
for(size_t rooti = begini; rooti<endi; ++rooti)
{
if(postorder[post_backi-posti]==inorder[rooti])
{
TreeNode* root = new TreeNode(inorder[rooti]);
++posti;
root->right = _buidTree(inorder,postorder,rooti+1,endi,posti);
root->left = _buidTree(inorder,postorder,begini,rooti,posti);
return root;
}
}
return nullptr;
}
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
size_t tmp = 0;
return _buidTree(inorder,postorder,0,inorder.size(),tmp);
}
};4. 二叉树的前序遍历二叉树（非递归）
题源：144. 二叉树的前序遍历 - 力扣（LeetCode）
给你二叉树的根节点
root，返回它节点值的 前序 遍历。（示例略，详情请点击题源链接查看）
提示：
- 树中节点数目在范围
[0, 100]内-100 <= Node.val <= 100进阶：递归算法很简单，你可以通过迭代算法完成吗？
题解
核心思路：用一个 stack 的对象去模拟递归的压栈和出栈。
从上图不难看出，整体的顺序为：根 → 左子树（递归……）→ 右子树（递归……），即对于这一层的根来说，先把左子树全部递归完成了，下调语句才开始执行右子树的递归。对于每一层来说都是如此，先去访问左树，再访问右树。而“根”递归到哪一层的“标志”。通过这样的分析，模拟压栈的思路就逐渐清晰了。
-
压栈：从上图不难看出，根 → 左子树 → 右子树，要先往下递归完左子树。因此，我们可以通过一个二叉树指针变量先去依次访问左支的结点，每访问到一个新的结点，就把这个结点压入栈中。（栈顶为哪个结点，则意味着递归到哪一层的结点。）
注意！栈里面存的是结点的指针不是结点值，二叉树的结点值有可能由重复。下图只是为了简化表达而看上去在栈里存储的是结点值。
-
出栈：根据 “ 根 → 左子树 → 右子树 ” 的递归顺序，对于该层的结点来说，根节点是最先被访问的，而当左子树被访问完了后我们就可以去访问该层结点的右子树，访问右子树将压入新的结点。因此，我们可以理解为——当访问到该层结点的右树时，该层结点就完成了“它的使命”，可以被出栈。
代码
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
if (root == nullptr)
return vector<int>();
vector<int> ret;
stack<TreeNode*> stp;
TreeNode* curp = root;//通过这个curp结点去遍历二叉树
while (curp || !stp.empty())
{
while (curp)
{
stp.push(curp);
ret.push_back(curp->val);//根
curp = curp->left;//左子树
}
// 左子树走到空结点
TreeNode* topp = stp.top(); // 以stack中的栈顶结点为根结点
stp.pop();
curp = topp->right;//右子树
}
return ret;
}
};5. 二叉树的中序遍历（非递归）
题源：94. 二叉树的中序遍历 - 力扣（LeetCode）
给定一个二叉树的根节点
root，返回 它的 中序 遍历 。（示例略，详情请点击题源链接查看）
提示：
- 树中节点数目在范围
[0, 100]内-100 <= Node.val <= 100
题解
相比于上一题的前序遍历很类似，只是对于当前层的结点我们要访问其左子树之后，再去访问根，此时才可以把访问到的这个根结点插入结果中。前序遍历是对于当前层的根结点，先把这个结点插入到结果中，再去向下递归左子树和右子树。
代码
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root)
{
if (root == nullptr)
return vector<int>();
vector<int> ret;
stack<TreeNode*> stp;
TreeNode* curp = root;
while (curp || !stp.empty())
{
while (curp)
{
stp.push(curp);
curp = curp->left;
}
// 左子树走到空结点
TreeNode* topp = stp.top(); // 以stack中的栈顶结点为根结点
stp.pop();
ret.push_back(topp->val);
curp = topp->right;//访问右子树
}
return ret;
}
};6. 二叉树的后序遍历（非递归）
题源：145. 二叉树的后序遍历 - 力扣（LeetCode）
给定一个二叉树的根节点
root，返回 它的 中序 遍历 。（示例略，详情请点击题源链接查看）
提示：
- 树中节点数目在范围
[0, 100]内-100 <= Node.val <= 100进阶: 递归算法很简单，你可以通过迭代算法完成吗？
题解
核心思路：同前面两题，即模拟递归出栈和入栈。
-
压栈：根据 “左子树 → 右子树 → 根” 的顺序，先要递归完左树（左树递归自己的左树再递归左树……直到递归到空）才会去递归本层的右树。
- 出栈：根据 “左子树 → 右子树 → 根” 的顺序，要递归完右树（或者右树为空不用递归），再去访问该层的根结点，访问该结点的方式就是把该结点从栈中弹出，输入到结果 ret 中。那么，问题的关键在于，如何判断该层结点的右子树是否被递归完。其右子树未被递归完则去递归右树，递归完了就访问该层的根节点。
根据后续遍历的顺序可知，如果前一个访问的结点是该层结点的右结点则意味着该层结点的右树已经完成递归访问。举例如下图。
（下图为了简便，更改了一直举例用的二叉树的。另外，上一个被访问的结点是需要用一个指针变量去记录的，而不是取 vector<int> ret 的末尾元素，下图只是为了表达方便画成这样。因为 ret 里面存的是结点值，前面的题有说过不能比较结点的值来判断，而要用结点的指针来判断）
代码
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
if (root == nullptr)
return vector<int>();
vector<int> ret;
stack<TreeNode*> stp;
TreeNode* curp = root;
TreeNode* prevp = nullptr;
while (curp || !stp.empty())
{
while (curp) // 递归，入栈
{
stp.push(curp);
curp = curp->left;//访问左树
}
// 左子树走到空结点
TreeNode* topp = stp.top(); // 取栈顶的元素，以stack中的栈顶结点为根结点
// topp->left == nullptr
// 是否需要访问右子树？
if((topp->right==nullptr)||(topp->right == prevp))
//如果右子树为空或者右子树已经被访问过，则这个根结点可以被pop
{
ret.push_back(topp->val);
stp.pop();//pop出topp,出栈
prevp = topp;//栈顶更新了，才需要去记录前一个栈顶的元素
}
else
//如果右子树不为空且右子树未被访问
{
curp = topp->right;//则去访问这个根结点以下的右子树
//当需要去递归新的子树，才需要去更新curp
//代码执行到这里，curp肯定原本为空指针，不更新curp则不会再去执行“递归，入栈”的循环
}
}
return ret;
}
};- 二叉树非递归遍历总结*
核心：“非递归”的本质是模仿递归的过程。递归两个关键动作就是——压栈和出栈。
在“非递归”的写法中，结合下图分析。到达root层即为压栈的动作，返回root层即为取栈顶的动作，当后续不必返回root层时，便可以出栈。在前序遍历和中序遍历中，当我们完成取栈顶的动作后，由于后面不需要再返回root层，即后续操作无需再使用root，因此我们可以直接pop(root)，随后继续递归root的右树；而对于后序遍历，则有两次返回root层的过程，因此当我们取到栈顶时，需要判断这是第一次还是第二次返回root，这个次序决定我们是否选择接下来去递归右树。
如上，我们可以感受到。相比于“非递归”的写法，递归的写法具有的 天然的语序优势 让我们不用去反复判断递归进行到哪一步了。例如，用递归的写法实现后序遍历时，就不需要判断这是第几次返回root层，因为递归会按语句的顺序依次执行——当它执行完左树的递归，会自然地进入右树的递归。
END