LeetCode題目：重建二叉樹

題目描述：

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

例如，給出

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

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

傳回如下的二叉樹：

限制：

0 <= 節點個數 <= 5000

來源：力扣（LeetCode）

連結：https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof

著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

解題思路：

LeetCode的題解裡面有這道題很詳細的解析，但是仍然需要說明一下，起碼是我看起來有點吃力的地方：

1、TreeNode本身在軟體裡面是一個接口（我用的是Eclipse 1.8），是以照着題目裡面TreeNode的自定義類輸入，是無法執行個體化的，必須要改個名字（我改成了TreeNode1）。

2、要注意裡面位置的描述：in_left，in_right是在說中序周遊裡面的左子樹和右子樹的邊界，左子樹邊界in_left到根節點之間的節點是左子樹包含的節點，根節點到右子樹邊界之間的節點是右子樹包含的節點。

3、回溯裡面的思想是将左子樹和右子樹的第一個節點作為根節點，這樣後面跟着的又是一個二叉樹，隻是新的二叉樹的左右邊界有所改變。

題目分析：

前序周遊特點： 節點按照

[ 根節點 | 左子樹 | 右子樹 ]

排序，以題目示例為例：

[ 3 | 9 | 20 15 7 ]

中序周遊特點： 節點按照

[ 左子樹 | 根節點 | 右子樹 ]

排序，以題目示例為例：

[ 9 | 3 | 15 20 7 ]

根據題目描述

輸入的前序周遊和中序周遊的結果中都不含重複的數字

，其表明樹中每個節點值都是唯一的。

• 根據以上特點，可以按順序完成以下工作：
  1. 前序周遊的首個元素即為根節點

     root

     的值；
  2. 在中序周遊中搜尋根節點

     root

     的索引 ，可将中序周遊劃分為

     [ 左子樹 | 根節點 | 右子樹 ]

     。
  3. 根據中序周遊中的左（右）子樹的節點數量，可将前序周遊劃分為

     [ 根節點 | 左子樹 | 右子樹 ]

     。
• 自此可确定 三個節點的關系 ：1.樹的根節點、2.左子樹根節點、3.右子樹根節點（即前序周遊中左（右）子樹的首個元素）。

子樹特點： 子樹的前序和中序周遊仍符合以上特點，以題目示例的右子樹為例：前序周遊：

[20 | 15 | 7]

，中序周遊

[ 15 | 20 | 7 ]

。

• 根據子樹特點，我們可以通過同樣的方法對左（右）子樹進行劃分，每輪可确認三個節點的關系 。此遞推性質讓我們聯想到用 遞歸方法 處理。

遞歸解析：

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

  pre_root

  、中序周遊左邊界

  in_left

  、中序周遊右邊界

  in_right

  。
• 終止條件： 當

  in_left > in_right

  ，子樹中序周遊為空，說明已經越過葉子節點，此時傳回 nullnullnull 。
• 遞推工作：
  1. 建立根節點

     root

     ： 值為前序周遊中索引為

     pre_root

     的節點值。
  2. 搜尋根節點

     root

     在中序周遊的索引

     i

     ： 為了提升搜尋效率，本題解使用哈希表

     dic

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

     root

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

     recur()

     方法開啟下一層遞歸。
     • 左子樹： 根節點索引為

       pre_root + 1

       ，中序周遊的左右邊界分别為

       in_left

       和

       i - 1

       。
     • 右子樹： 根節點索引為

       i - in_left + pre_root + 1

       （即：根節點索引 + 左子樹長度 + 1），中序周遊的左右邊界分别為

       i + 1

       和

       in_right

       。
• 傳回值： 傳回

  root

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

  root

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

以下圖解展示了題目示例樹的建立全流程。

1 / 9

代碼（Java）：

public class Solution {
	public static void main(String[] args) {
		int[] preorder = {3,9,20,15,7};
		int[] inorder = {9,3,15,20,7};
		TreeNode1 node = buildTree(preorder, inorder);//調試
		System.out.println();
	}
	
	static HashMap<Integer, Integer> dic = new HashMap<>();
    static int[] po;
    
    public static TreeNode1 buildTree(int[] preorder, int[] inorder) {
        po = preorder;
        for(int i = 0; i < inorder.length; i++)  //把前序周遊裡面的元素确定在中序周遊裡面的位置，便于确認左子樹，右子樹的長度
            dic.put(inorder[i], i);
        return recur(0, 0, inorder.length - 1);
    }
    
    //in_left和in_left都是元素在中序周遊裡面的位置，分表代表左子樹邊界和右子樹邊界，左子樹邊界到根節點，是構成左子樹的元素 ，根節點到右子樹邊界，是構成右子樹的元素
    public static TreeNode1 recur(int pre_root, int in_left, int in_right) {
        if(in_left > in_right) return null;
        TreeNode1 root = new TreeNode1(po[pre_root]);
        int i = dic.get(po[pre_root]);
        root.left = recur(pre_root + 1, in_left, i - 1); //這裡又看做是新的一個二叉樹，左子樹的第一個節點作為根節點，這樣左子樹的左邊界不會變，右邊界就變成原來根節點的前面一個 節點了
        root.right = recur(pre_root + (i - in_left) + 1, i + 1, in_right);  //這裡又看做是新的一個二叉樹，右子樹的第一個節點作為根節點，這樣右子樹的右邊界不會變，左邊界就變成原來根節點的後面一個 節點了
        return root;                   //i和in_left都是在中序周遊裡面的位置，是以這兩個要連在一起考慮，i是根節點的位置，in_left是左子樹的邊界，相減就是左子樹節點的範圍，
        							  //目前的根節點pre_root加上這個範圍就是位置最靠後的左子樹節點，加一就跳到右子樹的第一個節點
    }
	
}
           

題目描述：

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

例如，給出

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

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

傳回如下的二叉樹：

限制：

0 <= 節點個數 <= 5000

來源：力扣（LeetCode）

連結：https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof

著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

解題思路：

LeetCode的題解裡面有這道題很詳細的解析，但是仍然需要說明一下，起碼是我看起來有點吃力的地方：

1、TreeNode本身在軟體裡面是一個接口（我用的是Eclipse 1.8），是以照着題目裡面TreeNode的自定義類輸入，是無法執行個體化的，必須要改個名字（我改成了TreeNode1）。

2、要注意裡面位置的描述：in_left，in_right是在說中序周遊裡面的左子樹和右子樹的邊界，左子樹邊界in_left到根節點之間的節點是左子樹包含的節點，根節點到右子樹邊界之間的節點是右子樹包含的節點。

3、回溯裡面的思想是将左子樹和右子樹的第一個節點作為根節點，這樣後面跟着的又是一個二叉樹，隻是新的二叉樹的左右邊界有所改變。

題目分析：

前序周遊特點： 節點按照

[ 根節點 | 左子樹 | 右子樹 ]

排序，以題目示例為例：

[ 3 | 9 | 20 15 7 ]

中序周遊特點： 節點按照

[ 左子樹 | 根節點 | 右子樹 ]

排序，以題目示例為例：

[ 9 | 3 | 15 20 7 ]

根據題目描述

輸入的前序周遊和中序周遊的結果中都不含重複的數字

，其表明樹中每個節點值都是唯一的。

• 根據以上特點，可以按順序完成以下工作：
  1. 前序周遊的首個元素即為根節點

     root

     的值；
  2. 在中序周遊中搜尋根節點

     root

     的索引 ，可将中序周遊劃分為

     [ 左子樹 | 根節點 | 右子樹 ]

     。
  3. 根據中序周遊中的左（右）子樹的節點數量，可将前序周遊劃分為

     [ 根節點 | 左子樹 | 右子樹 ]

     。
• 自此可确定 三個節點的關系 ：1.樹的根節點、2.左子樹根節點、3.右子樹根節點（即前序周遊中左（右）子樹的首個元素）。

子樹特點： 子樹的前序和中序周遊仍符合以上特點，以題目示例的右子樹為例：前序周遊：

[20 | 15 | 7]

，中序周遊

[ 15 | 20 | 7 ]

。

• 根據子樹特點，我們可以通過同樣的方法對左（右）子樹進行劃分，每輪可确認三個節點的關系 。此遞推性質讓我們聯想到用 遞歸方法 處理。

遞歸解析：

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

  pre_root

  、中序周遊左邊界

  in_left

  、中序周遊右邊界

  in_right

  。
• 終止條件： 當

  in_left > in_right

  ，子樹中序周遊為空，說明已經越過葉子節點，此時傳回 nullnullnull 。
• 遞推工作：
  1. 建立根節點

     root

     ： 值為前序周遊中索引為

     pre_root

     的節點值。
  2. 搜尋根節點

     root

     在中序周遊的索引

     i

     ： 為了提升搜尋效率，本題解使用哈希表

     dic

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

     root

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

     recur()

     方法開啟下一層遞歸。
     • 左子樹： 根節點索引為

       pre_root + 1

       ，中序周遊的左右邊界分别為

       in_left

       和

       i - 1

       。
     • 右子樹： 根節點索引為

       i - in_left + pre_root + 1

       （即：根節點索引 + 左子樹長度 + 1），中序周遊的左右邊界分别為

       i + 1

       和

       in_right

       。
• 傳回值： 傳回

  root

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

  root

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

以下圖解展示了題目示例樹的建立全流程。

1 / 9