Pythonのプレオーダートラバーサルから二分探索木を構築する

指定されたプレオーダートラバーサルに一致するバイナリ検索ツリーを作成する必要があるとします。したがって、事前注文トラバーサルが[8,5,1,7,10,12]のような場合、出力は[8,5,10,1,7、null、12]になるため、ツリーは-になります。

これを解決するには、次の手順に従います-

• root：=0 ^th プレオーダートラバーサルリストのノード
• stack：=スタック、およびルートをスタックにプッシュします
• プレオーダーリストの2番目の要素の各要素iについて
  • 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

入力

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

出力

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