我试图解决这个问题:”给定一棵二叉树,检查他的前序访问并构建一个具有相同前序访问的二叉搜索树。演示是否总是可能的,如果不是则给出一个例子当这不可能。” 有什么帮助吗?我需要编写伪代码并给出时间复杂度,但我对构建对每个可能的二叉树具有相同预序访问的二叉搜索树有很多疑问。
最佳答案
如果您使用经典算法在二叉搜索树中插入,即执行搜索并在搜索停止的找到的 NULL
指针上放置新节点,则只需插入一棵空树,预序序列就会生成一棵完全具有给定预序序列的二叉树。
试试吧。遍历任何前序序列并将其插入空树中,您将实现它。
希望能帮到你。欢迎来到堆栈溢出!
关于algorithm - 给定一个预序二叉树访问构造一个具有相同预序访问的二叉搜索树。 (如果可能的话),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/54170577/