非递归实现二叉树的前序、中序、后序遍历-创新互联
目录
非递归实现二叉树的前序遍历
非递归实现二叉树的中序遍历
非递归实现二叉树的后序遍历
根据二叉树的前序和中序遍历结果还原二叉树
根据二叉树的中序和后序遍历结果还原二叉树
非递归遍历需要借助栈。
非递归实现二叉树的前序遍历前序遍历：二叉树的前序遍历：按照访问根节点——左子树——右子树的方式遍历这棵树，而在访问左子树或者右子树的时候，我们按照同样的方式遍历，直到遍历完整棵树。
1. 如果树为空，直接返回
2. 如果树非空：从根节点位置开始遍历，因为前序遍历规则：根节点、左子树、右子树
a. 沿着根节点一直往左走，将所经过路径中的节点依次入栈，并访问。
b. 取栈顶元素，该元素取到后，其左子树要么为空，要么已经遍历，可以直接遍历该节点，对于该节点，其左子树已经遍历，该节点也已经遍历，剩余其右子树没有遍历，将其左子树当成一棵新的树开始遍历，继续a步骤
vectorpreorderTraversal(TreeNode* root) {
vectorv;
stackst;
TreeNode*cur = root;
while(cur || !st.empty())
{
//循环每走一次迭代，就是在访问一棵树的开始
//访问左路节点，左路节点入栈
while(cur)
{
st.push(cur);
v.push_back(cur->val);
cur = cur->left;
}
//取出节点，访问右路节点
TreeNode* top = st.top();
st.pop();
//子问题形式访问右子树
cur = top->right;
}
return v;
} 中序遍历：按照访问左子树——根节点——右子树的方式遍历这棵树，而在访问左子树或者右子树的时候我们按照同样的方式遍历，直到遍历完整棵树。
中序遍历中，从栈中弹出的节点，其左子树是访问完了，可以直接访问该节点，然后接下来访问右子树。
1. 如果树为空，直接返回
2. 如果树非空：从根节点位置开始遍历，因为前序遍历规则：左子树、根节点、右子树
a. 沿着根节点一直往左走，将所经过路径中的节点依次入栈，并访问。
b. 取栈顶元素，该元素取到后，其左子树要么为空，要么已经遍历，可以直接遍历该节点，对于该节点，其左子树已经遍历，该节点也已经遍历，剩余其右子树没有遍历，将其左子树当成一棵新的树开始遍历，继续a步骤
vectorinorderTraversal(TreeNode* root) {
vectorv;
stackst;
TreeNode*cur = root;
while(cur || !st.empty())
{
while(cur)
{
st.push(cur);
cur = cur->left;
}
TreeNode* top = st.top();
st.pop();
v.push_back(top->val);
cur = top->right;
}
return v;
} 后序遍历：按照访问左子树——右子树——根节点的方式遍历这棵树，而在访问左子树或者右子树的时候我们按照同样的方式遍历，直到遍历完整棵树。
后序遍历中，从栈中弹出的节点，我们只能确定其左子树肯定访问完了，但是无法确定右子树是否访问过。因此，我们在后序遍历中，引入了一个prev来记录历史访问记录。
1. 如果树为空，直接返回
2. 如果树非空：从根节点位置开始遍历，但此时根节点不能遍历，因为后序遍历规则：左子树、右子树、根节点
a. 沿着根节点一直往左走，将所经过路径中的节点依次入栈
b. 取栈顶元素，该元素取到后，其左子树要么为空，要么已经遍历，但是此时该节点不能遍历，除非其右子树不存在或者其右子树已经遍历，才可以遍历该节点，如果该节点右子树没有遍历，将其右子树作为一棵新的二叉树遍历，继续a
- 当访问完一棵子树的时候，我们用prev指向该节点。
- 这样，在回溯到父节点的时候，我们可以依据prev是指向左子节点，还是右子节点，来判断父节点的访问情况。
vectorpostorderTraversal(TreeNode* root) {
vectorv;
stackst;
TreeNode* cur = root;
TreeNode* prev = nullptr;
while(cur || !st.empty())
{
while(cur)
{
st.push(cur);
cur = cur->left;
}
TreeNode* top = st.top();
//现在需要确定的是是否有右子树，或者右子树是否访问过
//如果没有右子树，或者右子树访问完了，也就是上一个访问的节点是右子节点时
//说明可以访问当前节点
if(top->right == nullptr || top->right == prev)
{
v.push_back(top->val);
//更新历史访问记录，这样回溯的时候父节点可以由此判断右子树是否访问完成
prev = top;
st.pop();
}
else
{
//右子树没有访问过，访问右子树
cur = top->right;
}
}
return v;
} 1. 从前序遍历结果中获取到树的根节点
2. 在中序遍历结果中确定根节点的位置，按照该位置将中序遍历结果分为两部分
左半部分是根节点的左子树，递归创建根节点的左子树
右半部分是根节点的右子树，递归创建根节点的右子树
TreeNode* _buildTree(vector& preorder, vector& inorder,int& previ,int inbegin,int inend) {
if(inbegin >inend)
return NULL;
TreeNode* root = new TreeNode(preorder[previ]);
int rooti = inbegin;
while(rooti<= inend)
{
if(inorder[rooti] == preorder[previ])
break;
else
++rooti;
}
++previ;
//[inbegin rooti-1] rooti [rooti+1,inend]
root->left = _buildTree(preorder,inorder,previ,inbegin,rooti-1);
root->right = _buildTree(preorder,inorder,previ,rooti+1,inend);
return root;
}
TreeNode* buildTree(vector& preorder, vector& inorder) {
int previ = 0;
return _buildTree(preorder,inorder,previ,0,inorder.size()-1);
} 1. 从后序遍历结果中获取到树的根节点，注意：后序遍历规则：左子树、右子树、根节点，因此应该从后往前获取根节点
2. 在中序遍历结果中确定根节点的位置，按照该位置将中序遍历结果分为两部分
右半部分是根节点的右子树，递归创建根节点的右子树---->注意先要还原根的右子树
左半部分是根节点的左子树，递归创建根节点的左子树
TreeNode* _buildTree(vector& inorder, vector& postorder,int& posti,int inbegin,int inend) {
if(inbegin >inend)
return NULL;
TreeNode* root = new TreeNode(postorder[posti]);
int rooti = inbegin;
while(rooti<= inend)
{
if(postorder[posti] == inorder[rooti])
break;
else
++rooti;
}
--posti;
root->right = _buildTree(inorder,postorder,posti,rooti+1,inend);
root->left = _buildTree(inorder,postorder,posti,inbegin,rooti-1);
return root;
}
TreeNode* buildTree(vector& inorder, vector& postorder) {
int posti = postorder.size()-1;
return _buildTree(inorder,postorder,posti,0,inorder.size()-1);
} 你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
当前标题：非递归实现二叉树的前序、中序、后序遍历-创新互联
文章源于：http://myzitong.com/article/djgsph.html