二、相对困难一点的二叉树OJ题
第一题：从前序与中序遍历序列构造二叉树
力扣链接：力扣
题目要求：
给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
要构建二叉树首先要明白前序和中序的特点，首先前序遍历的第一个节点一定是根节点，然后我们在中序遍历中找到根节点，根节点的左边区间就是左子树，右边区间就是右子树，知道了这个我们就可以通过区间来构建二叉树了：
class Solution { public: TreeNode* _buildTree(vector<int>& pre, vector<int>& in,int ibegin,int iend,int& pi) { if (ibegin>iend) { return nullptr; } TreeNode* root = new TreeNode(pre[pi]); int rooti = ibegin; while (rooti<=iend) { if (pre[pi]==in[rooti]) { break; } else { ++rooti; } } ++pi; root->left = _buildTree(pre,in,ibegin,rooti-1,pi); root->right = _buildTree(pre,in,rooti+1,iend,pi); return root; } TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { if (preorder.size()!=inorder.size()) { return nullptr; } if (preorder.empty()||inorder.empty()) { return nullptr; } int pi = 0; return _buildTree(preorder,inorder,0,inorder.size()-1,pi); } };
首先我们需要判断前序的节点个数是否和中序的节点个数相等，如果连个数都不相等那么是无法构建二叉树的。如果两个序列中有一个为空或者同时为空，那么也是不能构建出来的。然后我们创建一个变量pi，这个变量用来记录前序中的根节点值的下标，我们要递归构建一颗二叉树需要知道中序的区间（因为每次从前序中拿到根节点需要在中序中寻找这个节点来划分左右区间），所以ibegin和iend用来记录区间下标，接下来进入函数，当begin==end的时候我们发现只有一个节点，这个时候就可以直接构建节点了，当begin小于end的时候构建需要递归左右子树，当begin大于end的时候就没有节点了需要返回空给上一个节点的左子树或者右子树。只要不满足递归返回要求，我们就先创建根节点，然后定义一个变量记录中序中根节点的位置，用这个下标分割出左子树和右子树，在创建当前节点的左子树之前一点要让记录根节点的下标pi++,左子树区间为[ibegin,rooti-1] 右子树区间为[rooti+1,iend]，左右子树链接完成返回当前节点即可，下面我们画一个递归图演示一下：
第二题：从中序与后序遍历序列构造二叉树
力扣链接：力扣
题目要求：
给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。
这道题和上一道题唯一的区别在于，后序遍历的最后一个节点是根，并且根据后序在中序找根是先从右子树然后才是左子树，下面我们代码实现一下：
class Solution { public: TreeNode* _buildTree(vector<int>& in, vector<int>& post,int ibegin,int iend,int& pi) { if (ibegin>iend) { return nullptr; } TreeNode* root = new TreeNode(post[pi]); int rooti = ibegin; while (rooti<=iend) { if (post[pi]==in[rooti]) { break; } else { ++rooti; } } --pi; root->right = _buildTree(in,post,rooti+1,iend,pi); root->left = _buildTree(in,post,ibegin,rooti-1,pi); return root; } TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) { if (inorder.size()!=postorder.size()) { return nullptr; } if (inorder.empty()||postorder.empty()) { return nullptr; } int pi = postorder.size()-1; return _buildTree(inorder,postorder,0,inorder.size()-1,pi); } };
第三题：非递归实现 二叉树的前序遍历
力扣链接：力扣
二叉树的递归实现前序遍历相信大家都会，那么非递归呢？其实非递归的思想也很简单，就是将根节点的所有左子树入栈并且同时将节点值放入数组，然后拿出栈顶元素用栈顶元素的右子树继续遍历，下面我们实现一下：
class Solution { public: vector<int> preorderTraversal(TreeNode* root) { vector<int> v; if (root==nullptr) { return v; } stack<TreeNode*> st; TreeNode* cur = root; while (cur||!st.empty()) { while (cur) { st.push(cur); v.push_back(cur->val); cur = cur->left; } TreeNode* tmp = st.top(); st.pop(); cur = tmp->right; } return v; } };
首先判断根节点是否为空，如果为空就返回空向量。我们用一个栈记录每次遍历的节点，cur去遍历子树，首先将树的所有子树入栈并且将节点的值入向量，然后看栈顶节点是否有右子树，有的话就遍历这个右子树，没有的话cur为空不进入小循环直接再次拿栈顶元素看是否有右子树，大循环的条件是当cur和栈不同时为空的时候进入循环，因为即使cur为空而栈不为空也说明有元素没有遍历完，下面我们画个图演示一下：
第四题：非递归实现 二叉树的中序遍历
力扣链接：力扣
中序遍历与前序遍历的区别在于，我们不能在遍历左子树的时候直接把节点的值入到向量中，而是等到出栈的时候在入，我们直接写代码：
class Solution { public: vector<int> inorderTraversal(TreeNode* root) { vector<int> v; if (root==nullptr) { return v; } stack<TreeNode*> st; TreeNode* cur = root; while (cur||!st.empty()) { while (cur) { st.push(cur); cur = cur->left; } TreeNode* tmp = st.top(); st.pop(); v.push_back(tmp->val); cur = tmp->right; } return v; } };
第五题：非递归实现二叉树的后序遍历
力扣链接：力扣
后序遍历相对于前序和中序来讲就比较难了，后序的区别在于我们拿到栈顶元素的时候要判断这个栈顶元素是否有右子树，如果有我们需要直接入右子树的节点值不能直接弹出，并且我们无法知道到底是什么时候把根节点弹出栈，下面我们直接通过代码解释如何处理这个问题：
class Solution { public: vector<int> postorderTraversal(TreeNode* root) { vector<int> v; if (root==nullptr) { return v; } stack<TreeNode*> st; TreeNode* cur= root; TreeNode* pre = nullptr; while (cur||!st.empty()) { while (cur) { st.push(cur); cur = cur->left; } TreeNode* tmp = st.top(); if (tmp->right==nullptr||tmp->right==pre) { st.pop(); v.push_back(tmp->val); pre = tmp; } else { cur =tmp->right; } } return v; } };
下面我们通过画图解释一下：
通过上图我们可以看到，只有当栈顶节点的右子树为空或者栈顶节点的右子树等于上一个出栈的节点，那么就说明此时一个有右子树的根节点遍历完了，可以将这个根节点出栈了。
第六题：按之字形顺序打印二叉树
题目要求：
给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替）
class Solution { public: vector<vector<int> > Print(TreeNode* pRoot) { vector<vector<int>> vv; if (pRoot==nullptr) { return vv; } stack<TreeNode*> st; queue<TreeNode*> q; bool flag = true; st.push(pRoot); while (!st.empty()) { int sz = st.size(); vector<int> v; for (int i = 0;i<sz;i++) { TreeNode* tmp = st.top(); st.pop(); v.push_back(tmp->val); if (flag) { if (tmp->left) { q.push(tmp->left); } if (tmp->right) { q.push(tmp->right); } } else { if (tmp->right) { q.push(tmp->right); } if (tmp->left) { q.push(tmp->left); } } } vv.push_back(v); while (!q.empty()) { st.push(q.front()); q.pop(); } flag = !flag; } return vv; } };
此题最重要的是控制左右子树入栈的顺序，因为是之字形所以第二层一定是从右向左的，而用队列刚好满足第一层到第二层的需求，那么后面的该如何控制呢？其实我们设置一个标志，满足这个标志就从左向右，不满足就从右向左入栈，然后我们要每次进入下一层遍历的时候将标志置为反，这样就实现每次都是相反方向。
总结
二叉树进阶的OJ题相对比初阶难了不少，大多数情况需要通过画图的方式去演示，所以我们在做这类题目的时候一定要先想清思路，思路清晰了答案也就显而易见了。
