Leetcode 105. Construct Binary Tree from Preorder and Inorder Traversal

https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

Construct Binary Tree from Preorder and Inorder Traversal - LeetCode

 

---

또 다시 만난  Binary Tree  문제입니다

여러 문제를 풀다보니까 이제야 Binary Tree의 구조가 입체적으로 조금이나마 그려지는 것 같습니다

 

 

이 문제의 핵심은 주어진 preorder에서 root 를 뽑고 inorder 재귀를 통해서 큰 binary tree의 문제를  왼쪽 오른쪽 나누고,

또 왼쪽에서 다시 오른쪽왼쪽을 나누고 오른쪽에서 왼쪽 오른쪽이 나뉘어지는 패턴을 반복하는 것이었습니다.

 

Source: https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/discuss/981152/Recursion-or-Explanation-%2B-Visuals-or-Python

 

이런 preorder과 inorder의 관계는  파악했지만 코드화하는데 애를 먹었는데요

여러 풀이를 보면서 Binary tree 의 코드가 어떻게 구성되는지 좀 더 깊게 알아보려 합니다

 

---

Recursive Approach _

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        if inorder:
            start = inorder.index(preorder.pop(0))
            root = TreeNode(inorder[start])
            root.left = self.buildTree(preorder,inorder[:start])
            root.right = self.buildTree(preorder,inorder[start+1:])
            return root

root, root.left, root.right 이렇게 3가지를 명시적이고 깔끔하게 제시해서 가독성이 좋은 것 같습니다

 

문제를 고민하면서 제일 했갈렸던 부분이 null 을 어떻게 추가하는지였는데, if inorder 이 None이 되면 자동으로 null값을 반환하기 때문에 다른 if 문이나 조건이 더해질 필요가 없었습니다.

 

Dict + Recursion + deque_

class Solution:
	def buildTree(self,preorder,inorder):
    	preorder = collections.deque(preorder)
        inorder_map = {n:i for i,n in enumerate(inorder)}
        
        def build_tree(start,end):
            if start > end:
            	return
            root_index = inorder_map[preorder.popleft()]
            root = TreeNode(inorder[root_index],build_tree(start,root_index-1),build_tree(root_index+1,end))
            return root
         return build_tree(0,len(inorder)-1)

 

deque를 사용해서 pop 할 때 시간효율성을 높이고 dict 인 inorder_map에서 index를 찾기 쉽도록 했습니다.