如何从中序遍历和后序遍历迭代构造二叉树？

Question

从中序遍历和后序遍历迭代构造二叉树。

我已经了解了如何使用递归来完成它，但我正在寻找一个迭代构造二叉树的答案。

我写了一个中序和前序的算法，但我想知道如何为中序和后序修改它？

注意：它是伪代码，“=”表示“==”

节点：

e: TElement
right: PNode (pointer to a Node)
left: PNode (pointer to a Node)

二叉树：

root: PNode

子算法树（前序，中序）

pre: preorder: Int[], inorder: Int[]

preOrderIndex<- 0;
inOrderIndex<-0;

Stack(s) 
root <- createNode(preorder[0])
push(s, root)

preOrderIndex<-preOrderIndex +1

While !empty(s)
    element(s, top) //which is the same as top = peak(s)
    
    if [top].e = inorder[inOrderIndex] 
        delete(s, top) //delete the element from the stack
        inOrderIndex<-inOrderIndex +1
    
        if inOrderIndex = length(inorder) 
            
            return root
        End if
        
        element(s, elem) 
        
        if !empty(s) and [elem].e = inorder[inOrderIndex]
            continue
        End if
        
       
        nod <- createNode(preorder[preOrderIndex])
        [top].right<-nod
        preOrderIndex<-preOrderIndex +1
        push(s,nod)
    Else
        nod <- createNode(preorder[preOrderIndex])
        [top].left<-nod
        preOrderIndex<-preOrderIndex +1
        push(s,nod)
    End if
End while

return root

结束子算法

编辑：我找到了答案

Answer 1

当你有一个给定前序和中序遍历的工作解决方案时，你可以使用以下观察将它变成一个给定后序和中序遍历的解决方案：

中序遍历的逆序等于镜像树的中序遍历（左右互换）
后序遍历的逆序等于镜像树的前序遍历

因此对您的工作算法进行以下更改：

将 pre 重命名为 post 在变量名称中出现的所有地方
用length(inorder)-1

postOrderIndex

inOrderIndex

用递减语句替换递增语句
将退出条件替换为if inOrderIndex < 0
将left替换为right，反之亦然

如何从中序遍历和后序遍历迭代构造二叉树？

How to construct a Binary Tree from Inorder and Postorder Traversal iteratively?

iteration

algorithm

tree

recursion

binary-tree