Zenn
🐙

NeetCode 150 [Trees]medium:preorder、inorderな配列から２分木を再構成する

に公開
trees
neetcode
tech

NeetCodeのSolutionを書いていく

Construct Binary Tree From Preorder And Inorder Traversal

問題

2つの整数の配列preorderとinorderが与えられます。
preorderは２分木をroot,left,rightの順番で訪れます。
inorderは２分木をleft,root,rightの順番で訪れます。

preorder、inorderのはいれつから２分木を作りそのrootを返しましょう。

例

Input: preorder = [1,2,3,4], inorder = [2,1,3,4]
Output: [1,2,3,null,null,null,4]

Input: preorder = [1], inorder = [1]
Output: [1]

制約

  • 1 <= inorder.length <= 1000.
  • inorder.length == preorder.length
  • -1000 <= preorder[i], inorder[i] <= 1000
  • 計算：O(n)
  • メモリ：O(n)

メモ

例としてはOutputは「Level Order」で表記しているのに、設問にはrootを返しましょうと記載がある。
どういうコッチャ？と思ったが、どうやらrootを返すとOutputと同じ形式で比較をしてくれるらしい。

ヒント1

inorderではrootが配列の中央あたりに来ます。またrootより左のデータは左の木に、右のデータは右の木に存在することがわかります。
ではrootはどれ？preorderを見るとわかります。
→ preorderの最初の値がrootである

ヒント2

  • ツリーの構築には深さ優先探索（DFS）を使用します。
  • グローバル変数は、前順序配列の現在のインデックスを追跡します。
  • インデックスlとrは、現在のサブツリーの順序配列内のセグメントを表します。
  • 前順序配列の各ノードに対してノードを作成し、ハッシュマップを使用して順序配列内のそのインデックスを見つけ、範囲[l, r]を左と右のサブツリーの2つの部分に分割することで、左と右のサブツリーを再帰的に構築します。

２分木の問題は解答がシンプルになって面白いですね。
頭で考えてもなかなか混乱して難しいですが。
そのうち自力で解けるようになるかな。

from typing import List, Optional


def list_to_tree(data):
    if not data:
        return None

    nodes = [TreeNode(val) if val is not None else None for val in data]
    child_index = 1
    for index in range(len(nodes)):
        node = nodes[index]
        if node is not None:
            if child_index < len(nodes):
                node.left = nodes[child_index]
                child_index += 1
            if child_index < len(nodes):
                node.right = nodes[child_index]
                child_index += 1
    return nodes[0]


# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        if not preorder or not inorder:
            return None

        # 最初のデータを格納する
        tree = TreeNode(preorder[0])

        mid = inorder.index(tree.val)

        # 左の木を再帰的に探す
        left_preorder_tree = preorder[1 : mid + 1]
        left_inorder_tree = inorder[0:mid]
        tree.left = self.buildTree(left_preorder_tree, left_inorder_tree)

        # 右の木を再帰的に探す
        right_preorder_tree = preorder[mid + 1 :]
        right_inorder_tree = inorder[mid + 1 :]
        tree.right = self.buildTree(right_preorder_tree, right_inorder_tree)

        return tree

Discussion