Aug 16, 2021

Leetcode 105 Construct Binary Tree from Preorder and Inorder Traversal

Soru

Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree.

Örnek 1





Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]

Örnek 2

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

Çözüm

Bu soruda, preorder ve inorder dizileri verilmiş, ve bu iki traversala göre binary tree’yi yeniden oluşturmamız isteniyor.
Binary Tree Traversal Özellikleri:
Preorder (Root - Left - Right): İlk eleman her zaman root’tur.
Inorder (Left - Root - Right): Root’un solundakiler sol subtree, sağındakiler sağ subtree’dir.
Preorder’daki ilk elemanı root olarak al.
Bu root elemanını inorder’da bul ve konumuna göre sol ve sağ alt ağaçları ayır.
Aynı işlemi recursive olarak sol ve sağ taraflar için uygula.

Code

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

        # Root node preorder'ın ilk elemanı
        root_val = preorder[0]
        root = TreeNode(root_val)

        # Root'un inorder'daki index'ini bul
        mid = inorder.index(root_val)

        # Sol ve sağ subtree'leri recursive olarak kur
        root.left = self.buildTree(preorder[1:1 + mid], inorder[:mid])
        root.right = self.buildTree(preorder[1 + mid:], inorder[mid + 1:])

        return root

Complexity

Optimize Edilmiş Versiyon (O(n) zaman)
inorder dizisindeki indeksleri bir hashmap ile önceden kaydedersen, her root’un index’ini O(1) sürede bulabilirsin:

Code

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        inorder_index_map = {val: idx for idx, val in enumerate(inorder)}
        self.preorder_index = 0

        def helper(left, right):
            if left > right:
                return None

            root_val = preorder[self.preorder_index]
            self.preorder_index += 1

            root = TreeNode(root_val)
            index = inorder_index_map[root_val]

            root.left = helper(left, index - 1)
            root.right = helper(index + 1, right)

            return root

        return helper(0, len(inorder) - 1)

Complexity

Time complexity (Zaman Karmaşıklığı) :O(n²) O(n²) çünkü inorder.index() her seferinde O(n) zaman alır, toplamda n kez çağrılır.
Space complexity (Alan Karmaşıklığı) :O(n)