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

Question

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

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

我为inorder和preorder编写了一个算法，但我想知道如何修改inorder和postorder的算法？

注意：它是伪代码，“=”意味着“==”

节点：

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

二叉树：

root: PNode

子算法树（前序、有序）

pre:preorder:Int[]，inoorder: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出现在变量名中的任何地方
• 初始化postOrderIndex和inOrderIndex与长度（inorder）-1
• 用递减语句替换递增语句
• 将退出条件替换为if inOrderIndex