105. Construct Binary Tree from Preorder and Inorder Traversal

Question: Construct Binary Tree from Preorder and Inorder Traversal
Solution

• preorder: 中 → 左 → 右。第一位永遠是 root
• inorder: 左 → 中 → 右。 找到 root 之，root 之前都是「left subtree」，root 之後都是「right subtree」

1. 依據 preorder 的第一位 preorder[0] 得知 root 是誰

2. 看 root 在 inorder 中的 index 位置，得知 left subtree & right subtree 分別有哪些

   • left subtree = inorder[頭 : root index]
   • right subtree = inorder[root index + 1 : 尾]

3. 由此推知 preorder 的 left subtree 與 right subtree 位置

   • left subtree: inorder 頭到 root index 的長度是 left subtree 的長度，那麼 preorder 由第一位(root)往後算起，加上 left subtree 的長度，就是 preorder 中 left subtree 的位置：preorder[1: left subtree 長度 + 1]
   • right subtree: 剩下的數字，也就是 left subtree 之後一直到尾巴：preorder[left subtree 長度 + 1: 尾巴]

4. build_tree function:

   subtree 的建立，一樣要回到「 root + left subtree + right subtree 」→ recursive build_tree

• 終止條件：

  如果 preorder 或 inorder 是空的，代表走到葉子: if not preorder: return None

• 遞回條件：

  如果 preorder 跟 inorder list 裡有東西，就要拿出來做 subtree

1. 建立 root
   • preorder 第一位: TreeNode(preorder[0])
2. 建立 left subtree
   • 把 preorder & inorder 的 left subtree 部分找出來，丟回 recursive function: root.left = build_tree(preorder, inorder)
3. 建立 right subtree
• 把 preorder & inorder 的 right subtree 部分找出來，丟回 recursive function: root.right = build_tree(preorder, inorder)

# Definition for a binary tree node.

class TreeNode:

def __init__(self, val=0, left=None, right=None):

self.val = val

self.left = left

self.right = right

class Solution:

def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:

if not preorder:

return None

root = TreeNode(preorder[0])

mid = inorder.index(preorder[0])

root.left = self.buildTree(preorder[1:mid + 1], inorder[: mid])

root.right = self.buildTree(preorder[mid + 1:], inorder[mid + 1:])

return root

Video Solution