在 Python 中根据前序遍历构建二叉搜索树

pythonserver side programmingprogramming更新于 2025/11/14 15:08:17

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

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

root := 前序遍历列表的第 0 个节点
stack := a stack，并将 root 推送到 stack
对于前序列表的第二个元素中的每个元素 i
- i := a值为 i 的节点
- 如果 i 的值 < 栈顶元素，则
  - 栈顶节点左侧 := i
  - 将 i 插入栈中
- 否则
  - 当栈不为空时，且栈顶元素值 < i 的值
    - 最后一个 := 栈顶
    - 从栈中弹出元素
  - 最后一个节点右侧 := 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