README.md

Construct Binary Tree from Preorder and Inorder Traversal

題目連結

題目描述

原文：

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.

---

GPT 4 翻譯：

給定兩個整數數組 preorder 和 inorder，其中 preorder 是一棵二元樹的前序遍歷，而 inorder 是同一棵樹的中序遍歷，構建並返回該二元樹。

---

Example 1

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

Example 2

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

Constraints:

• 1 <= preorder.length <= 3000
• inorder.length == preorder.length
• -3000 <= preorder[i], inorder[i] <= 3000
• preorder and inorder consist of unique values.
• Each value of inorder also appears in preorder.
• preorder is guaranteed to be the preorder traversal of the tree.
• inorder is guaranteed to be the inorder traversal of the tree.

思路

單獨一個 preorder 或 inorder 序列並不能構成唯一個樹，但如果同時給了這兩個序列就可以，而可以觀察一下這兩個序列，以 Example 1 為例，preorder 的第一個節點 3 會是根節點，並且對應到 inorder 第 index = 1 的位置，而 inorder 的特性剛好可以樹一分為二，代表 index < 1 的部分都是左子樹、index > 1 的部分都是右子樹。

所以，我們每一次從 preorder 拿一個節點出來，知道根節點為何，再拿去對應 inorder 序列，知道要從哪裡一分為二，不斷地遞迴下去。

方法: Recursive

• 步驟

  1. 建立一個 recursive 函式：
     1. Base Case: 當沒節點可挑時
     2. Recusive Case:
        1. node.left = dfs(起點, 一分為二的點 - 1)
        2. node.right = dfs(一分為二的點 + 1, 終點)

• 複雜度

  • 時間複雜度: O(N)
  • 空間複雜度: O(N)
    • 為了加快搜尋速度，會先將 inorder 序列儲存在 Hashmap 裡 -> O(N)
    • 樹在遞迴的平均高度為 logN -> O(logN)