目录
6. 根据一棵树的前序遍历与中序遍历构造二叉树
题目
分析
代码
7. 根据一棵树的中序遍历与后序遍历构造二叉树
题目
分析
代码
8. 二叉树的前序遍历，非递归迭代实现
题目
分析
代码
9. 二叉树中序遍历 ，非递归迭代实现
题目
分析
代码
10. 二叉树的后序遍历 ，非递归迭代实现
题目
分析
代码
6. 根据一棵树的前序遍历与中序遍历构造二叉树
题目
OJ链接
分析
前序遍历的第一个结点一定是根节点，根据根结点在中序结点的位置可以划分出根节点的左右结点范围，然后根据递归调用，不断地划分子树的左右结点，代码如下
代码
class Solution {
public:
TreeNode* createTree(vector<int>& preorder, vector<int>& inorder,int& cur,int begin,int end)
{
if (begin > end)
return nullptr;
int root = begin;
//寻找根节点在中序遍历的位置
while (root <= end)
{
if (preorder[cur] == inorder[root])
break;
++root;
}
TreeNode* ret = new TreeNode(preorder[cur++]);
ret->left=createTree(preorder, inorder, cur, begin, root-1);
ret->right=createTree(preorder, inorder, cur, root+1, end);
return ret;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
if (preorder.empty() || inorder.empty())
return nullptr;
int cur=0;
int begin = 0;
int end = inorder.size() - 1;
return createTree(preorder, inorder,cur,begin,end);
}
};7. 根据一棵树的中序遍历与后序遍历构造二叉树
题目
OJ链接
分析
方法跟上一题类似，只是后续遍历的根节点要从最后一位找，并且向前遍历，同时要注意先找右子树再找左子树。
代码
class Solution {
public:
TreeNode* createTree(vector<int>& postorder, vector<int>& inorder, int& cur, int begin, int end)
{
if (begin > end)
return nullptr;
int root = begin;
while (root <= end)
{
if (postorder[cur] == inorder[root])
break;
++root;
}
TreeNode* ret = new TreeNode(postorder[cur--]);
ret->right = createTree(postorder, inorder, cur, root + 1, end);
ret->left = createTree(postorder, inorder, cur, begin, root - 1);
return ret;
}
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
if (postorder.empty() || inorder.empty())
return nullptr;
int cur = inorder.size() - 1;
int begin = 0;
int end = cur;
return createTree(postorder, inorder, cur, begin, end);
}
};8. 二叉树的前序遍历，非递归迭代实现
题目
OJ链接
分析
任意一个树我们都可以分为两部分：左路结点和左路结点的右子树，如下图
左路结点的右子树又可以分为新的左路结点和左路结点的右子树
通过这种思路，如下代码所示
代码
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> ans;
if (root == nullptr)
return ans;
TreeNode* cur = root;
stack<TreeNode*> st;
while (!st.empty()||cur)
{
//插入所有左路结点到栈中
while (cur)
{
st.push(cur);
ans.push_back(cur->val);
cur = cur->left;
}
//对左路结点进行出栈，并将左路结点的右子树的根作为新的cur结点
//下一层循环访问右子树的所有左路结点插入到栈中
TreeNode* top = st.top();
st.pop();
cur = top->right;
}
return ans;
}
};9. 二叉树中序遍历 ，非递归迭代实现
题目
OJ链接
分析
将上一题的ans.push_back放到下面既可以完成
代码
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> ans;
if (root == nullptr)
return ans;
TreeNode* cur = root;
stack<TreeNode*> st;
while (!st.empty()||cur)
{
while (cur)
{
st.push(cur);
cur = cur->left;
}
TreeNode* top = st.top();
st.pop();
ans.push_back(top->val);
cur = top->right;
}
return ans;
}
};10. 二叉树的后序遍历 ，非递归迭代实现
题目
OJ链接
分析
因为是后序遍历，父亲结点最后插入，所以要判断右结点是否为空或者右结点是上一次访问过的结点
代码
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> ans;
if (root == nullptr)
return ans;
TreeNode* prenode = nullptr;
TreeNode* cur = root;
stack<TreeNode*> st;
while (!st.empty() || cur) {
while (cur) {
st.push(cur);
cur = cur->left;
}
TreeNode* top = st.top();
if (top->right == nullptr || prenode == top->right) {
st.pop();
ans.push_back(top->val);
prenode = top;
} else {
cur = top->right;
}
}
return ans;
}
};
