时间戳

首页 > 解决方案 > 如何迭代地从中序和后序遍历构造二叉树？

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

问题描述

从 Inorder 和 Postorder Traversal 迭代地构造二叉树。

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

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

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

节点：

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

二叉树：

root: PNode

子算法树（前序，中序）

pre：预购：Int[]，中序：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

结束子算法

编辑：我找到了答案

标签： algorithmrecursiontreeiterationbinary-tree

解决方案

当您有一个给定前序和中序遍历的工作解决方案时，您可以使用以下观察将其转换为给定后序和中序遍历的解决方案：

  • 中序遍历的逆序等于镜像树的中序遍历（左右交换）

  • 后序遍历的逆序等于镜像树的前序遍历

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

  • 重命名pre为post变量名中出现的任何地方
  • 初始化postOrderIndex并inOrderIndex使用length(inorder)-1
  • 用递减语句替换它们的递增语句
  • 将退出条件替换为if inOrderIndex < 0
  • 替换left为right，反之亦然

推荐阅读