# LeetCode Medium 105. Construct Binary Tree from Preorder and Inorder Traversal

tags: leetcode

最近の疑問としてPythonの関数内関数は出来るだけ使わない方がいいのかということがあります…(便利そうだし今後はもう少し使うことにしようかな…？)

問題

• Explore
• Problems

アイデア

preorderのBSTとinorderのBSTが与えられた時に，BSTを構築しろという問題です．

これ系はおそらく暗記というか，ノリを理解していつでも実装出来るようにすれば良さそう？

解法

inorderではBSTを左部分木→ノード→右部分木という風に走査します．そのため，inorder_dic(inorder_dic[val] := idx)を使います．

この連想配列から取り出したvalue(index)より小さいvalue(index)のノードは左部分木，大きいものは右部分木に属します．そのためコレを使って再帰的に木を構築します．

preorderはノード→左部分木→右部分木という走査の仕方をするので，先頭から上の処理をする必要があります．

計算量

inorder, postorderのノードの数をそれぞれ$N$，$M$とし，木の深さを$H$とします．

• 時間計算量
  • 連想配列を作るのに，$O(N)$
  • 再帰関数の実行に$O(M)$
  • $O(N + M)$
• 空間計算量
  • 連想配列に$O(N)$
  • 再帰関数で$O(H)$
  • $O(N + H)$

Python

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
from typing import Dict

class Solution:
    cnt = 0
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        inorder_dic = {}
        for idx, val in enumerate(inorder):
            inorder_dic[val] = idx
        return self._rec_build(0, len(inorder)-1, preorder, inorder_dic)
        
    def _rec_build(self, low: int, high: int, preorder: List[int], inorder_dic: Dict[int, int]) -> TreeNode:
        if low > high:
            return None
        mid_node = TreeNode(preorder[self.cnt])
        self.cnt += 1
        mid = inorder_dic[mid_node.val]
        mid_node.left = self._rec_build(low, mid-1, preorder, inorder_dic)
        mid_node.right = self._rec_build(mid+1, high, preorder, inorder_dic)
        return mid_node