leetcode medium : Construct Binary Tree from Preorder and Inorder Traversal

Construct Binary Tree from Preorder and Inorder Traversal - LeetCode

Construct Binary Tree from Preorder and Inorder Traversal - LeetCode

 

와 이게 무슨 미디엄이냐 너무 어려운데..

일단 내생각엔 이 과정으로 문제를 해결해야한다.

1. 현재 tree의 루트노드값을 찾고 이걸로 노드를 만든다.

2. 루트노드값을 찾으면 이걸 기준으로 inorder list를 left와 right로 나눌 수 있다. 

3. 각 left와 right 리스트에 대해 알고리즘을 재귀적으로 수행한다.

 

문제는 left right가 나눠져갈 때 어떻게 루트노드를 빨리 찾을 것인가다..

뭔가 알듯말듯한데 확실하게 정리가 안된다. 아 면접보는데 이런문제 나오면 진짜 큰일나는데 ㅠ

 

아?

나 문제이해를 잘못하고

잘못 이해한 상태로 문제를 풀었다.

preorder 순서를 착각했네?

나 preorder 순서를 level order traversal로 생각해버렸다;;

하 ㅋㅋㅋㅋㅋ

preorder가 아니라 level order traversal이면 솔루션은 다음과 같다 ㅋㅋㅋㅋㅋㅋ

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        
        val_ind = dict()
        for i in range(len(inorder)):
            val_ind[inorder[i]] = i
        
        
        root_node = TreeNode(preorder[0])
        cur_level_nodes = [(root_node, 0, len(inorder) - 1)]
        
        pointer = 1
        
        while cur_level_nodes:
            nxt_level_nodes = []
            
            for node, low, high in cur_level_nodes:
                i_ind = val_ind[node.val]
                
                if i_ind > low and i_ind < high:
                    node.left = TreeNode(preorder[pointer])
                    pointer += 1
                    node.right = TreeNode(preorder[pointer])
                    pointer += 1
                    
                    nxt_level_nodes.append((node.left, low, i_ind - 1))
                    nxt_level_nodes.append((node.right, i_ind + 1, high))
                elif low == high:
                    continue
                elif i_ind == low:
                    node.right = TreeNode(preorder[pointer])
                    pointer += 1
                    
                    nxt_level_nodes.append((node.right, i_ind + 1, high))
                elif i_ind == high:
                    node.left = TreeNode(preorder[pointer])
                    pointer += 1
                    
                    nxt_level_nodes.append((node.left, low, i_ind - 1))
                    
            cur_level_nodes = nxt_level_nodes
            
        return root_node

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ아니..

 

나 뭐하냐고 진짜 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

 

다시 풀자.

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        
        #inorder list value to inorder list index
        ii = dict()
        for i in range(len(inorder)):
            ii[inorder[i]] = i
        
        root_node = TreeNode(preorder[0])
        
        nodestack = [(root_node, 0, len(inorder) - 1)]
        
        for i in range(len(preorder)):
            node, low, high = nodestack.pop()
            node.val = preorder[i]
            
            root_i = ii[node.val]
            
            if root_i < high:
                node.right = TreeNode()
                nodestack.append((node.right, root_i + 1, high))
            if root_i > low:
                node.left = TreeNode()
                nodestack.append((node.left, low, root_i - 1))
        
        return root_node

 

ㅋㅋㅋ 착각하고 빡세게 고민했던거 덕분에 그래도 이건 쉽게 풀었다.

iterative solution이라서 memory usage가 미쳤구만

 

inorder 리스트에서 현재 루트노드를 찾으면 좌측과 우측 값들을 보고 left subtree가 있는지 right subtree가 있는지 알수있다. right , left 순서로 스택에 추가하고 스택에서 하나씩 pop시키면서 노드를 만들어나가면 preorder 순서대로 값을 부여할 수 있다. 

 

recursive solution이 아마 가독성은 더 좋을듯.

 

다른사람 솔루션 보자

 

def buildTree(self, preorder, inorder):
    def build(stop):
        if inorder and inorder[-1] != stop:
            root = TreeNode(preorder.pop())
            root.left = build(root.val)
            inorder.pop()
            root.right = build(stop)
            return root
    preorder.reverse()
    inorder.reverse()
    return build(None)

우왕 이게 뭐냐..

뭔가 알듯말듯.. 아리송하네.. 이건 내일 아침에 마저 보고 공부해야겠다. 내일 일찍 일어나야돼서..