# LeetCode Medium 106. Construct Binary Tree from Inorder and Postorder Traversal

tags: leetcode

問題

• Explore
• Problems

アイデア

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

木の探索順序

木を探索する際の順序として以下の図ように

• Inorder(左→根→右)
• Preorder(根→左→右)
• Postorder(左→右→根)

があります

ノードが5つの木の場合を図示すると以下の通りです

Inorderに木を走査する際は

• 基底は現在のノードがNULL(葉の次についているノード)であるときに終了する
• 現在のノードがNULLでないときは左部分木に進み, 現在のノードの値をansに入れる, 右部分木に進むということを繰り返します
  • これによって左の部分木のノードが先に入り, 次に右の部分木のノードが入ります

順序に注目すると

postorderの最後の要素は根となります．

inorderは左部分木→ノード→右部分木と走査するので，inorderで根の左側は左部分木，右側は右部分木です．

解法

• 上のアイデアを配列を用いて実装すると計算量が無駄にかかります
• 計算量改善のため，連想配列を用いて実装します．
• postorderの末尾から走査することで，ノード→右部分木→左部分木と見ることになります．
• midから見て，右部分木，左部分木を再帰関数recを使って構築していきます．
• lowとhighは走査するノードのinorderでのindexを見ていて，これが逆転して場合，走査する範囲を超えたことを表します．

計算量

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

class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
        inorder_dic = {}
        for i, val in enumerate(inorder):
            inorder_dic[val] = i
        return self.rec(0, len(inorder)-1, postorder, inorder_dic)
        
    def rec(self, low, high, postorder, inorder_dic):
        if low > high:
            return None
        x = TreeNode(postorder.pop())
        mid = inorder_dic[x.val]
        x.right = self.rec(mid+1, high, postorder, inorder_dic)
        x.left = self.rec(low, mid-1, postorder, inorder_dic)
        return x