Python 中从先序遍历构造二叉搜索树

假设我们必须创建一个与给定先序遍历匹配的二叉搜索树。因此，如果先序遍历类似于 [8,5,1,7,10,12]，则输出将为 [8,5,10,1,7,null,12]，因此树将为 -

为了解决这个问题，我们将遵循以下步骤 -

• root := 先序遍历列表的第 0 个节点
• stack := 一个栈，并将根节点压入栈中
• 对于先序列表的第二个元素开始的每个元素 i
  • i := 一个值为 i 的节点
  • 如果 i 的值 < 栈顶元素的值，则
    • 栈顶节点的左子节点 := i
    • 将 i 插入到栈中
  • 否则
    • 当栈不为空，且栈顶元素的值 < i 的值时
      • last := 栈顶
      • 从栈中弹出元素
    • 最后一个节点的右子节点 := i
    • 将 i 插入到栈中
• 返回根节点

让我们看看以下实现以更好地理解 -

示例

class Solution(object):
   def bstFromPreorder(self, preorder):
      """
      :type preorder: List[int]
      :rtype: TreeNode
      """
      root = TreeNode(preorder[0])
      stack = [root]
      for i in preorder[1:]:
         i = TreeNode(i)
         if i.val<stack[-1].val:
            stack[-1].left = i
            stack.append(i)
         else:
            while stack and stack[-1].val<i.val:
               last = stack.pop(-1)
            last.right = i
            stack.append(i)
      return root

输入

[8,5,1,7,10,12]

输出

[8,5,10,1,7,null,12]

Arnab Chakraborty

更新于: 2020年5月2日

686 次浏览

开启您的 职业生涯

通过完成课程获得认证

开始学习