面試位元組跳動時，我竟然遇到了原題……

今天分享的題目來源于 LeetCode 上的劍指 Offer 系列 面試題07. 重建二叉樹，近半年在位元組跳動算法面試環節出現過高達 14 次，你很可能遇到過，它屬于中高難度的算法題，今天吳師兄和你一起弄懂！

題目連結：https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/solution/mian-shi-ti-07-zhong-jian-er-cha-shu-di-gui-fa-qin/

一、題目描述

輸入某二叉樹的前序周遊和中序周遊的結果，請重建該二叉樹。假設輸入的前序周遊和中序周遊的結果中都不含重複的數字。

例如，給出

前序周遊 preorder = [3,9,20,15,7]
中序周遊 inorder = [9,3,15,20,7]      

傳回如下的二叉樹：

3
   / \
  9  20
    /  \
   15   7      

限制：

​

​0 <= 節點個數 <= 5000​

​

二、題目解析

首先，我們先來複習一下前序周遊、中序周遊。（在下方的視訊中分布講解）

前序周遊

二叉樹的前序周遊順序是：根節點、左子樹、右子樹，每個子樹的周遊順序同樣滿足前序周遊順序。

中序周遊

二叉樹的中序周遊順序是：左子樹、根節點、右子樹，每個子樹的周遊順序同樣滿足中序周遊順序。

複習過後，我們可以得出以下結論：

• 在二叉樹的前序周遊 序列中，第一個數字總是樹的根結點的值；
• 在二叉樹的中序周遊 序列中，根結點的值在序列的中間，左子樹的結點的值位于根結點的值的左邊，而右子樹的結點的值位于根結點的值的右邊

以本題的序列為例，前序周遊序列的第一個數字 3 就是根結點的值，在中序周遊序列，找到根結點值的位置。根據中序周遊特點，在根結點的值 3 前面的數字都是左子樹結點的值，在根結點的值 3 後面的數字都是右子樹結點的值。

二叉樹很重要的一個性質是遞歸，在找到了左子樹、右子樹的前序周遊序列和中序周遊序列後，我們可以按照同樣的方法去确定 子左子樹 和 子右子樹 的建構。

具體的代碼編寫思路如下（來源于 Krahets's Blog）：

• 遞推參數： 前序周遊中根節點的索引​

  ​pre_root_idx​

  ​、中序周遊左邊界​

  ​in_left_idx​

  ​、中序周遊右邊界​

  ​in_right_idx​

  ​。
• 終止條件： 當 ​

  ​in_left_idx &gt; in_right_idx​

  ​ ，子樹中序周遊為空，說明已經越過葉子節點，此時傳回 null 。
• 遞推工作：

1. 建立根節點 root ： 值為前序周遊中索引為​

   ​pre_root_idx​

   ​的節點值。
2. 搜尋根節點 root 在中序周遊的索引 i ： 為了提升搜尋效率，本題解使用哈希表 ​

   ​map​

   ​ 預存儲中序周遊的值與索引的映射關系，每次搜尋的時間複雜度為 O(1)。
3. 建構根節點​

   ​root​

   ​的左子樹和右子樹：通過調用  ​

   ​recursive()​

   ​  方法開啟下一層遞歸。

• 左子樹： 根節點索引為 pre_root_idx + 1 ，中序周遊的左右邊界分别為 in_left_idx 和 i - 1。
• 右子樹： 根節點索引為 i - in_left_idx + pre_root_idx + 1（即：根節點索引 + 左子樹長度 + 1），中序周遊的左右邊界分别為 i + 1 和 in_right_idx。
• 傳回值： 傳回 ​

  ​root​

  ​，含義是目前遞歸層級建立的根節點 ​

  ​root​

  ​ 為上一遞歸層級的根節點的左或右子節點。

三、動畫描述

四、圖檔描述

五、參考代碼

class Solution {
    //在中序序列中查找與前序序列首結點相同元素的時候，如果使用 while 循環去一個個找效率很慢
    //這裡我們借助資料結構 HashMap 來輔助查找，在開始遞歸之前把所有的中序序列的元素和它們所在的下标存到一個 map 中，這樣查找的時間複雜度是 O(logn)
    HashMap<Integer, Integer> map = new HashMap<>();

    //保留的前序周遊
    int[] preorder;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        //在開始遞歸之前把所有的中序序列的元素和它們所在的下标存到一個 map 中
        for (int i = 0; i < preorder.length; i++) {
            map.put(inorder[i], i);
        }
        //二叉樹的重要性質是遞歸
        return recursive(0,0,inorder.length-1);
    }

    /** 根據前序周遊序列和中序周遊序列重新組建二叉樹
     * @param pre_root_idx 前序周遊的索引
     * @param in_left_idx  中序周遊左邊界的索引
     * @param in_right_idx 中序周遊右邊界的索引
     */
    public TreeNode recursive(int pre_root_idx, int in_left_idx, int in_right_idx) {

        //子樹中序周遊為空，說明已經越過葉子節點，此時傳回 nul
        if (in_left_idx > in_right_idx) {
            return null;
        }

        //root_idx是在前序裡面的
        TreeNode root = new TreeNode(preorder[pre_root_idx]);

        // 通過 map ，根據前序的根節點的值，在中序中擷取目前根的索引
        int idx = map.get(preorder[pre_root_idx]);

        //左子樹的根節點就是 左子樹的(前序周遊）第一個，就是 +1 ,左邊邊界就是 left ，右邊邊界是中間區分的idx-1
        root.left = recursive(pre_root_idx + 1, in_left_idx, idx - 1);

        //右子樹的根，就是右子樹（前序周遊）的第一個,就是目前根節點 加上左子樹的數量
        root.right = recursive(pre_root_idx + (idx-1 - in_left_idx +1)  + 1, idx + 1, in_right_idx);

        return root;
    }
}      

這段代碼的一個難點就是 ​

​root.left​

​​ 與 ​

​root.right​

​ ，我這裡抽離出來詳細解釋一下。

1、root.left

2、root.right

六、複雜度分析

時間複雜度

時間複雜度為 O(N)。

空間複雜度

空間複雜度為 O(N)。

七、相關标簽

• 樹
• 遞歸
• 哈希表

八、參考來源

• 1、https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/solution/mian-shi-ti-07-zhong-jian-er-cha-shu-di-gui-fa-qin/ 題解區
• 2、https://krahets.gitee.io/views/sword-for-offer/2020-02-24-sword-for-offer-07.html

由 五分鐘學算法 原班人馬打造的公衆号：圖解面試算法，現已正式上線！
接下來我們将會在該公衆号上，為大家分享優質的算法解題思路，堅持每天一篇原創文章的輸出，視訊動畫制作不易，感興趣的小夥伴可以關注點贊一下哈！