LeetCode 105. Construct Binary Tree from Preoder and Inorder Traversal

November 28, 2024

Happy Thanksgiving! I am happy to have solved this without looking up a solution. However, I did have to review traversals.

Solution

1from collections import deque
2
3# Definition for a binary tree node.
4# class TreeNode:
5#     def __init__(self, val=0, left=None, right=None):
6#         self.val = val
7#         self.left = left
8#         self.right = right
9class Solution:
10    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
11        top = deque(preorder)
12        bottom = deque(inorder)
13        nodes = []
14        seen = set()
15
16        root = parent = TreeNode()
17        while top:
18            parent.right = TreeNode(top.popleft())
19            left = parent.right
20            seen.add(left.val)
21            nodes.append(left)
22            while left.val != bottom[0]:
23                left.left = TreeNode(top.popleft())
24                left = left.left
25                seen.add(left.val)
26                nodes.append(left)
27            while bottom and bottom[0] in seen:
28                bottom.popleft()
29                parent = nodes.pop()
30            
31        return root.right

Time complexity is O(n) = n and space complexity is O(n) due to set and deques.

LeetCode 146. LRU Cache

LeetCode 236. Lowest Common Ancestor of a Binary Tree