---
# System prepended metadata

title: 二元樹操作
tags: [資料結構]

---

---
title: '二元樹操作'
disqus: kyleAlien
---

二元樹操作
===

## OverView of Content

[TOC]

## 二元樹 - 基礎

二元樹基礎框架如下，接下來我們都會以框架出發，來解決問題

```java=
class TreeNode {
    TreeNode left, right;
    int val;
    
    public TreeNode(int val) {
        this.val = val;
    }

}


// 二元樹 遞迴框架
void traverse(TreeNode node) {
    traverse(node.left);
    traverse(node.right);
}
```

### 二元樹 - 走訪框架

* 二元樹框架如下，不同的題目會針對不同的走訪（前序、中序、後序）

    ```java=
    public class BaseModule {

        private static final class TreeNode {
            TreeNode left, right;
            int value;
        }

        public void recursive(TreeNode node) {
            // TODO: 前序走訪
            recursive(node.left);
            // TODO: 中序走訪
            recursive(node.right);
            // TODO: 後序走訪
        }

    }
    ```

### 多元樹 - 走訪框架

* 二元樹尋訪框架可以拓展為 N 元樹的尋訪框架

    ```java=

    public class BaseModule {

        private static final class TreeNode {
            TreeNode[] children;
            int value;
        }

        public void recursive(TreeNode node) {
            for(TreeNode item : children) {
                // 遞迴
                recursive(item);
            }
        }

    }
    ```
    :::info
    * N 元樹尋訪又可稱為，**圖的尋訪**，因為 **圖就是好幾個 N 元樹的結合**
        
        > 出現環循環？ 使用一個陣列標記已訪問過得節點即可
    :::

### 基礎控制 -  Node 加一

* 以下我們先做一個簡單的二元樹，至於二元樹的建構規則我們下一節在說

    ```java=
    public class TreeNode {

        TreeNode left, right;
        int val;

        public TreeNode(int val) {
            this.val = val;
        }

        public TreeNode(int val, TreeNode left, TreeNode right) {
            this(val);

            this.left = left;
            this.right = right;
        }

        public static TreeNode getBaseTreeNode() {
            TreeNode four = new TreeNode(4);
            four.left = new TreeNode(3);

            TreeNode two = new TreeNode(2, new TreeNode(1), four);
            TreeNode six = new TreeNode(6, null, new TreeNode(7));

            return new TreeNode(5, two, six);
        }

    }
    ```
    建構出的二元樹圖如下
    > ![](https://i.imgur.com/IxE7MQj.png)

* 現在將上面二元樹上的 **每個節點 val + 1**，套用框架可以簡單的解決這件事

    ```java=
    public class BaseControl {

        public void addEveryNode(TreeNode root) {
            // base case (遞迴都有一個 base case)
            if(root == null) {
                return;
            }

            System.out.print("Old: " + root.val);
            root.val += 1;
            System.out.println(", New: " + root.val);

            addEveryNode(root.left);
            addEveryNode(root.right);
        }

        public static void main(String[] args) {
            BaseControl baseControl = new BaseControl();

            baseControl.addEveryNode(TreeNode.getBaseTreeNode());
        }

    }
    ```
    > ![](https://i.imgur.com/pzctpk1.png)


### 基礎控制 - 比較兩個樹

* 現在來比較兩個 Tree 是否相同，**同樣注意這裡的 base case** (**換位思考一下最底端，也就是末端時，你要如何處理方法的返回**)

    1. 兩個 root 都為 null，返回 true
        > ![](https://i.imgur.com/IoOI2Mu.png)


    2. 兩個 root 只有其中一個為 null，這就不相符，返回 false
        > ![](https://i.imgur.com/W2zOATD.png)

    
    3. 兩者 Node 節點的數據不相同，這個不用說一定返回 false

        ```java=
        public class CompareTree {

            public boolean isSameTree(TreeNode root1, TreeNode root2) {
                if(root1 == null && root2 == null) {
                    return true;
                }

                if(root1 == null || root2 == null) {
                    return false;
                }

                if(root1.val != root2.val) {
                    return false;
                }

                boolean leftTree = isSameTree(root1.left, root2.left);

                boolean rightTree = isSameTree(root1.right, root2.right);

                // 皆為 true
                return leftTree && rightTree;
            }

            public static void main(String[] args) {
                TreeNode tree1 = TreeNode.getBaseTreeNode();
                TreeNode tree2 = TreeNode.getBaseTreeNode();

                CompareTree compareTree = new CompareTree();
                boolean result = compareTree.isSameTree(tree1, tree2);

                System.out.println("Is same tree: " + result);
                // -----------------------------------------------------------------


                tree2.left = new TreeNode(1);
                boolean result2 = compareTree.isSameTree(tree1, tree2);

                System.out.println("Is same tree: " + result2);
            }

        }
        ```
    > ![](https://i.imgur.com/ypsIJvw.png)

## 二元樹 - 規則

> 二元樹的排序是有規則的，按照規則來進行排序

1. **右子樹任意節點 (Node)，要大於等於 ++左子樹++的 ==所有== 節點**

2. **左子樹任意節點 (Node)，要小於等於 ++右子樹++的 ==所有== 節點**

### 二元樹 vs. Heap 規則

* Heap 也是使用二元分治法，不過它的規則 與 二元樹不同，**Heap 不是一個合法的二元樹**

* 二元樹 vs. Heap 規則不同點
    
    1. **入隊方式**

        * Heap：**從末端 Tail 入隊**，之後針對新數值進行 swim 上浮作業

        * 二元樹：**從起始端 Header 入隊**，比較當前節點，**小於放置左側子樹、大於放置右測子樹** (最終可以達到左子樹全部節點都比右子樹任一節點小)

            > ![](https://i.imgur.com/TRG2auH.png)

    2. **樹形狀**

        * Heap：限制必須是 **完全 or 滿二元樹** (一定會有左節點才會有右節點)

        * 二元樹：沒有限制，可以傾斜，不規則
            
            > ![](https://i.imgur.com/7nyBPB8.png)
    
    3. **Child Node 節點規則**

        * Heap：不可以比 Parent 節點大

        * 二元樹：不可以比 Parent 節點大、**並且左子樹的所有節點都小於右子樹的任一節點** (Heap 無法達到這個規則)
            > ![](https://i.imgur.com/swwj2aR.png)



### 判斷 BST 合法性 - 錯誤

* 以下我們用框架，寫一個常常會發生問題的 二元樹合法性判斷，**由於該二元樹基於遞迴，所以一項先考慮 base case**

    > 以下範例是錯誤的判斷
    ```java=
    // 有問題的 二元樹合法判斷

        boolean isValidTree_Problem(TreeNode root) {
            // base case 1
            if(root == null) {
                return true;
            }

            // base case 2
            if(root.left != null && root.val <= root.left.val) {
                // 判斷 當前 Node 不該小於 小於等於 左 Node
                return false;
            }

            // base case 3
            if(root.right != null && root.val >= root.right.val) {
                // 判斷 當前 Node 不該小於 大於等於 右 Node
                return false;
            }

            boolean leftTree = isValidTree_Problem(root.left);
            boolean rightTree = isValidTree_Problem(root.right);

            return leftTree && rightTree;
        }
    ```
    
    * 這裡問題在於 Node 必須比較子樹的 **所有節點 (這個所有就是重點!)，並符合條件**; 像是以圖就可以演示這個問題
        
        > ![](https://i.imgur.com/9VjLsbZ.png)
        
        ```java=
        public static void main(String[] args) {
            CheckValid checkValid = new CheckValid();

            TreeNode sub = new TreeNode(15, new TreeNode(9), new TreeNode(20));
            TreeNode treeNode = new TreeNode(10, new TreeNode(2), sub);


            boolean result = isValid.isValidTree_Problem(treeNode);
            System.out.println("Is valid result: " + result);
        }        
        ```
        這個測試結果有問題，這棵 Tree 應該不合法 !

        > ![](https://i.imgur.com/mGphGZ4.png)

        上述測試的問題點：**根結點 10 應該小於全部右子樹的節點 (這樣 9 就不符合)**，**++應該返回 false 才對++**
        
        > ![](https://i.imgur.com/mwE7T2r.png)


### 判斷 BST 合法性 - 輔助參數 - 正確

* 看到上面錯誤的範例，並且我們也發現了問題，就可以針對問題作修正

* 這邊我們使用 **輔助參數**，**增加方法函數的參數**，透過該參數進行判斷是否符合二元樹規則。為了解決這個問題

    :::success
    * 這個參數是用來 **約束**：限制每個 Node 的區間，**有點類似於左右指針**
        
        1. 對於左子樹：**右指針內縮 (限制最大值)**，也就是所有左子樹節點 node < root
        
        2. 對於右子樹：**左指針內縮 (限制最小值)**，也就是所有右子樹節點 node > root
    :::

    ```java=
    boolean isValidTree(TreeNode root, TreeNode min, TreeNode max) {
        if(root == null) {    // 已到末端
            return true;
        }

        if(max != null && root.val >= max.val) {
            return false;
        }

        if(min != null && root.val <= min.val) {
            return false;
        }

        // 傳入 root，限制最大值
        boolean leftTree = isValidTree(root.left, min, root);
        
        // 傳入 root，限制最小值
        boolean rightTree = isValidTree(root.right, root, max);

        // 左右子樹必須都符合，所以使用 `&&`
        return leftTree && rightTree;
    }
    ```
    
    :::warning
    * 參數傳遞：
        
        看似相同，但是差異在 **會傳遞 min、max**，比較的數值就會有 min、max 兩個 !
        
    :::
    
    > ![](https://i.imgur.com/n6tJ1Pg.png)

    ```java=
    public static void main(String[] args) {
        CheckValid checkValid = new CheckValid();

        TreeNode sub = new TreeNode(15, new TreeNode(9), new TreeNode(20));
        TreeNode treeNode = new TreeNode(10, new TreeNode(2), sub);

        // -----------------------------------------------------------------------------------

        boolean result2 = checkValid.isValidTree(treeNode, null, null);
        System.out.println("Is valid result with 9: " + result2);

        sub.left = new TreeNode(11);
        boolean result3 = checkValid.isValidTree(treeNode, null, null);
        System.out.println("Is valid result with 13: " + result3);
    }
    ```
    > ![](https://i.imgur.com/cLcctlX.png)


### BST 尋找指定數 - 遞迴

BST 二元搜尋，以下我們使用這棵樹
> ![](https://i.imgur.com/b2xbbKH.png)

* 由於使用遞迴，所以重點仍先放在 ^1.^ base case (只要 base case 正確就對了一半)，另一半是 ^2.^ 返回的結果

    ```java=
    public class IsExist {

        public boolean isExist(TreeNode treeNode, int target) {
            // 找到末端仍沒找到
            if(treeNode == null) {
                return false;
            }

            // 找到直接返回
            if(treeNode.val == target) {
                return true;
            }

            boolean leftTree = isExist(treeNode.left, target);
            boolean rightTree = isExist(treeNode.right, target);

            // 返回使用 `||` (其中一個找到即可)
            return leftTree || rightTree;
        }

        public static void main(String[] args) {
            TreeNode baseTreeNode = TreeNode.getBaseTreeNode();

            IsExist isExist = new IsExist();

            boolean result = isExist.isExist(baseTreeNode, 4);
            System.out.println("Is 4 in tree ? " + result);

            boolean result2 = isExist.isExist(baseTreeNode, 99);
            System.out.println("Is 99 in tree ? " + result2);
        }
    }
    ```
    
* **使用 2 分法優化**：由於我們知道 2 元樹規則，比較 `root.val` & `target` 後就能完全排除 `target` 在另外一邊的可能性
    ```java=
    public boolean isExist_Opt(TreeNode treeNode, int target) {
        if(treeNode == null) {
            return false;
        }

        if(treeNode.val == target) {
            return true;
        }

        if(treeNode.val > target) {
            return isExist(treeNode.left, target);
        }

        return isExist(treeNode.right, target);
    }

    public static void main(String[] args) {
        TreeNode baseTreeNode = TreeNode.getBaseTreeNode();

        IsExist isExist = new IsExist();

        boolean result = isExist.isExist_Opt(baseTreeNode, 4);
        System.out.println("Is 4 in tree ? " + result);

        boolean result2 = isExist.isExist_Opt(baseTreeNode, 99);
        System.out.println("Is 99 in tree ? " + result2);
    }
    ```
    > ![](https://i.imgur.com/PJxYFsP.png)


### BST 尋找指定數 - 非遞迴 (迭代)

BST 二元搜尋，以下我們使用這棵樹
> ![](https://i.imgur.com/b2xbbKH.png)

* 除了上面的遞迴方法以外，我們也可以使用非遞迴的方式搜尋該二元樹

    ```java=
    public boolean isExit_traverse(TreeNode treeNode, int target) {
        TreeNode tmp = treeNode;

        while (tmp != null) {
            if(tmp.val == target) {
                return true;
            }

            if(tmp.val > target) {
                tmp = tmp.left;
            } else {
                tmp = tmp.right;
            }
        }

        return false;
    }


    public static void main(String[] args) {
        TreeNode baseTreeNode = TreeNode.getBaseTreeNode();

        IsExist isExist = new IsExist();

        boolean result = isExist.isExit_traverse(baseTreeNode, 4);
        System.out.println("Is 4 in tree ? " + result);

        boolean result2 = isExist.isExit_traverse(baseTreeNode, 99);
        System.out.println("Is 99 in tree ? " + result2);

    }
    ```
    > ![](https://i.imgur.com/nnAnQmW.png)


### BST 插入一個數

以下我們使用這棵樹
> ![](https://i.imgur.com/b2xbbKH.png)

* **資料結構的操作，無非是尋訪 (找)、存取 (改)**；如果要改就是先進行 `找`，找到目標節點後，再進行 `改` (也就是插入)

    :::info
    1. 一旦涉及 **改**：方法就 **必須返回 `TreeNode` 類型**，並 **接收遞迴呼叫地返回值**
    2. 這裡也可以使用 **2 分概念** (分治法)
    :::
    
    ```java=
    public class InsertNode {

        TreeNode insertNode(TreeNode root, int newVal) {
            if(root == null) {
                // 返回值會接到末端節點上
                return new TreeNode(newVal);
            }

            if(root.val == newVal) {
                return root;
            }

            if(newVal < root.val) {
                root.left =  insertNode(root.left, newVal);
            }

            if(newVal > root.val) {
                root.right = insertNode(root.right, newVal);
            }

            return root;
        }
    }
    ```
    
* 測試 `insertNode` 插入新數據

    ```java=
    // 中序走訪 (測試用
    private void recursivePrint(TreeNode node) {
        if(node == null) {
            return;
        }
        recursivePrint(node.left);
        System.out.print(node.val + ", ");
        recursivePrint(node.right);
    }

    public static void main(String[] args) {
        TreeNode baseTreeNode = TreeNode.getBaseTreeNode();

        InsertNode t = new InsertNode();
        t.insertNode(baseTreeNode, 10);
        t.insertNode(baseTreeNode, 8);

        t.recursivePrint(baseTreeNode);
    }
    ```
    > ![](https://i.imgur.com/4eDPXyN.png)

    :::info
    * 以不同順序插入二元樹會對於最終二元樹圖形的結果有影響

        如果以遞增順序插入，則效率會最差，會轉為一個 偏移傾斜二元樹；這時找尋一個數值就會耗費 O(N) 的時間

        > ![](https://i.imgur.com/YpN4Sid.png)
    :::

### BST 刪除指定 Node

* BST 刪除指定 Node 就稍微複雜一點，依照規則需要考慮三種情況 (**如果是 N 元樹就有 N! 個狀況**)
    
    :::success
    由於刪除也涉及 `改`，所以必須返回 `TreeNode` 類型
    :::

    ```java=
    // 套用基礎框架

    public class DeleteNode {

        public TreeNode deleteNode(TreeNode root, int deleteKey) {

            if(root.val == deleteKey) {
                // TODO: 找到目標節點，準備進行刪除
                return root;
            }

            if(root.val > deleteKey) {
                // 左子樹，串上刪除後的結果
                root.left = deleteNode(root.left, deleteKey);
            }

            if(root.val < deleteKey) {
                // 右子樹，串上刪除後的結果
                root.right = deleteNode(root.right, deleteKey);
            }

            return root;
        }

    }
    ```
    
    1. **刪除末端 Node**：這是一個 base case，重點是判斷左右節點都為 Node (代表是末端)
        
        ```java=
        // 左右皆為 null 代表末端

        if(root.left == null && root.right == null) {
            return null;    // 返回 null，就是斷開節點
        } 
        ```
        
        > ![](https://i.imgur.com/9MR7Yxu.png)

    2. **刪除 Node 有一個子樹**：把下一個子樹的數值全部複製 (有就是返回下一個子樹即可)

        ```java=
        // 左子樹不為空
        if(root.left != null) {
            // root.val = root.left.val;    // 手動交換
            // root.left = root.left.left;
            // return root;
            
            return root.left;    // 同上 `手動交換`
        }

        // 右子樹不為空
        if(root.right != null) {
            // root.val = root.right.val;    // 手動交換
            // root.right = root.right.right;
            // return root;
            
            return root.right; // 同上 `手動交換`
        }
        ```
        
        > ![](https://i.imgur.com/CAR8f1V.png)

    3. **刪除 Node 有兩個子樹（難）**：**為了不破壞二元樹的規則**，以下有兩種方案 (都以刪除 `2` 這個 Node 為目標)；**找左最大、找右最小，使用其中一個即可**
        
        * **左子樹：必須找到 ++左子樹中 ==最大==++ 的節點來交換**
            > 2 跟 1 交換
            > 
            > ![](https://i.imgur.com/5kjwHXB.png)

            ```java=
            // 左子樹方案

            // 左右皆有子樹
            if(root.left != null && root.right != null) {
                TreeNode maxNode = getMax(root.left);    // 找左子樹中最大
                root.val = maxNode.val;        // 交換數值 (2 -> 1)，就當作交換了節點

                root.left = deleteNode(maxNode);    // 刪除最小 (1)
            }

            TreeNode getMax(TreeNode node) {
                // 按照規則，最右邊的 Node 就是 BST 中最大的數 !!!
                // 如果沒有右節點，自然是當前的節點
                while(node.right != null) {
                    node = node.right;
                }
                return node;
            }
            ```

        * **右子樹：必須找到 ++右子樹中 ==最小==++ 的節點來交換**
            > 2 跟 3 交換
            > 
            > ![](https://i.imgur.com/Qcrb7dt.png)

            ```java=
            // 右子樹方案

            // 左右皆有子樹
            if(root.left != null && root.right != null) {
                TreeNode minNode = getMin(root.right);    // 找右子樹中最小
                root.val = minNode.val;        // 交換數值 (3 -> 4)，就當作交換了節點

                root.right = deleteNode(minNode);    // 刪除最小 (3)
            }

            TreeNode getMin(TreeNode node) {
                // 按照規則，最左邊的 Node 就是 BST 中最小的數 !!!
                while(node.left ! null) {    
                    node = node.left;
                }
                return node;    
            }
            ```
            
        :::warning
        * 這裡用簡單的交換 val 值來代表節點已交換
        :::

* 將上面的三種情況做整理再寫出完整的 BST 樹刪除指定節點 (以下使用找右子樹中最小)

    ```java=
    public class DeleteNode {

        public TreeNode deleteNode(TreeNode root, int deleteKey) {
            // base case
            if(root == null) {
                return null;
            }

            if(root.val == deleteKey) {

                // 目標結點是否是末端節點
                if(root.right == null && root.left == null) {
                    // 返回 null，讓原節點串上
                    return null;
                }

                // 有其中一個為 null
                if(root.left == null) {    // 沒有左子樹
                    // 返回右子樹
                    return root.right;
                }

                if(root.right == null) {    // 沒有右子樹
                    // 返回左子樹
                    return root.left;
                }

                // 有左、右子樹
                TreeNode minNode = getMin(root.right);    // 目前使用，找右子樹中最小
                root.val = minNode.val;

                root.right = deleteNode(root.right, minNode.val);
            }

            if(root.val > deleteKey) {
                root.left = deleteNode(root.left, deleteKey);
            }

            if(root.val < deleteKey) {
                root.right = deleteNode(root.right, deleteKey);
            }

            return root;
        }

        private TreeNode getMin(TreeNode node) {
            
            while (node.left != null) {
                // 最小要往左找 !
                node = node.left;
            }
            return node;
        }

    }
    ```
    * 測試移除下圖中 `5` 這個節點
        
        > ![](https://i.imgur.com/vXgL0L8.png)

        ```java=
        public static void main(String[] args) {
            TreeNode baseTreeNode = TreeNode.getBaseTreeNode();

            DeleteNode deleteNode = new DeleteNode();
            TreeNode result = deleteNode.deleteNode(baseTreeNode, 5);

            // 前序走訪
            TreeNode.traverse(result);
        }
        ```
        > ![](https://i.imgur.com/wDMdCzH.png)

:::info
* 另一種作法：請看註解

    ```java=
    public class DeleteNode_2 {

        public TreeNode deleteNode(TreeNode root, int deleteKey) {
            // base case
            if(root == null) {
                return null;
            }


            if(root.val > deleteKey) {
                root.left = deleteNode(root.left, deleteKey);

            } else if(root.val < deleteKey) {
                root.right = deleteNode(root.right, deleteKey);

            } else if(root.val == deleteKey) {

                // 無左右子樹
                if(root.right == null && root.left == null) {
                    return null;
                }

                // 無左子樹
                if(root.left == null) {
                    // 返回右
                    return root.right;
                }

                // 無右子樹
                if(root.right == null) {
                    // 返回左
                    return root.left;
                }

                TreeNode tmp = root;

                // 先找到右子樹中最小 Node，準備重新串接
                root = root.right;
                while (root.left != null) {
                    root = root.left;
                }

                // 找到後移除右子樹的最小
                // 將剛剛找到的最小 Node，並移除，重新串上右子樹
                root.right = removeMin(tmp.right);
                
                // 將剛剛找到的最小 Node，重新串上左子樹
                root.left = tmp.left;
            }

            return root;
        }

        // 移除最小
        private TreeNode removeMin(TreeNode node) {
            if(node.left == null) {
                return node.right;
            }
            // 最終 node#left 左會串上 node#right
            node.left = removeMin(node.left);
            return node;
        }

        // 結果
        public static void main(String[] args) {
            TreeNode baseTreeNode = TreeNode.getBaseTreeNode();

            DeleteNode_2 d2 = new DeleteNode_2();
            TreeNode result = d2.deleteNode(baseTreeNode, 5);

            TreeNode.traverse(result);
        }
    }
    ```
    > ![](https://i.imgur.com/egZEHiW.png)

:::

## 二元樹分類


### 完全二元樹

* 每一層都緊靠左邊，如果有其中一層 **無緊靠左側 (若沒有緊靠左側，就不是完整二元樹)**，則不是完全二元樹

    > 類似於 Heap 的規則
    
    > ![](https://i.imgur.com/i2s0YU3.png)

    :::success
    * 英文的完全二元樹是 **Complete Binary Tree**
    :::

### 滿二元樹

* 每一層的元素都是滿的

    > ![](https://i.imgur.com/4snGIZ9.png)

    :::success
    * 英文的滿二元樹是 **Perfect Binary Tree**
    :::

## Node 數量


### 普通二元樹 - Node 數量
計算以下二元樹

> ![](https://i.imgur.com/4h1sQ9K.png)

```java=
public class NormalTree {

    public int getNormalTreeCount(TreeNode root) {
        if(root == null) {
            return 0;
        }

        int leftCount = getNormalTreeCount(root.left);

        int rightCount = getNormalTreeCount(root.right);

        return leftCount + rightCount + 1;      // add self
    }
    

    public static void main(String[] args) {
        TreeNode treeNode = TreeNode.getBaseTreeNode();

        NormalTree normalTree = new NormalTree();
        int result = normalTree.getNormalTreeCount(treeNode);

        System.out.println("Normal tree count: " + result);
    }
}
```

:::info
* 只要經過一個節點，就將結點總數量 + 1
:::

**--實作結果--**
> ![](https://i.imgur.com/N7MV7yC.png)

### 滿二元樹 - Node 數量
計算以下二元樹

> ![](https://i.imgur.com/iuX6tbM.png)

* 滿二元樹可以跳脫框架進行更快速的計算，規則如下：**滿二元樹總結點數量為：==2^高度^ - 1==**，所以首先計算該樹的高，然後透過公式就可以取得滿二元樹的數量

    :::info
    * 滿多元樹的 Node 總數量則是，(分支^高度^) - (分支 - 1)
    :::

    ```java=
    public class PerfectTree {

        public int getPerfectTreeCount(TreeNode root) {

            int height = 0;
            while (root != null) {
                root = root.left;   // same as right
                height++;
            }

            return (int) (Math.pow(2, height) - 1);
        }

        public static void main(String[] args) {
            PerfectTree perfectTree = new PerfectTree();

            TreeNode leftTree = new TreeNode(2, new TreeNode(1), new TreeNode(4));
            TreeNode rightTree = new TreeNode(7, new TreeNode(6), new TreeNode(8));
            TreeNode tree = new TreeNode(5, leftTree, rightTree);

            int result = perfectTree.getPerfectTreeCount(tree);

            System.out.println("Perfect tree count: " + result);

        }
    }
    ```
    **--實作結果--**
    > ![](https://i.imgur.com/2kM3NtH.png)

### 完全二元樹 - Node 數量
計算以下二元樹

> ![](https://i.imgur.com/fOaqrhq.png)

* **完全二元樹，其實又跟滿二元樹相同。所以完全二元樹 = 普通二元樹 + 滿二元樹的測量**

    ```java=
    public class CompleteTree {

        public int getCompleteTree(TreeNode root) {
            TreeNode left = root;
            TreeNode right = root;

            int leftH = 0;
            while (left != null) {        // 算左子樹最高
                left = left.left;
                leftH++;
            }

            int rightH = 0;
            while (right != null) {        // 算右子樹最高
                right = right.right;
                rightH++;
            }

            // 完美二元樹
            if(rightH == leftH) {
                System.out.println("Prefect");
                return (int) Math.pow(2, rightH) - 1;
            }

            // `1` 是自身
            return 1 + getCompleteTree(root.left) + getCompleteTree(root.right);
        }

        public static void main(String[] args) {
            CompleteTree completeTree = new CompleteTree();

            TreeNode leftTree = new TreeNode(2, new TreeNode(1), new TreeNode(4));
            TreeNode rightTree = new TreeNode(7, new TreeNode(6), null);
            TreeNode tree = new TreeNode(5, leftTree, rightTree);

            int result = completeTree.getCompleteTree(tree);

            System.out.println("Perfect tree count: " + result);
        }

    }
    ```
    **--實作--**
    > ![](https://i.imgur.com/dP7yi3O.png)

* **BIG O 大小：這種寫法的重點是從根結點開始的左、右子樹，只有一個會真正往下去做，另一個則會執行滿二元樹**

    1. 遞迴演算法對於樹的高度為 `O(logN)`
    
    2. 每次遞迴所花費的時間為 while 計算高度，計算高度的時間為 `O(2 * logN)`
    
    3. 最終使用時間為 `O(2 * logN logN)`
    
    > ![](https://i.imgur.com/hGfKe87.png)

## 序列化 & 反序列化 BST

```java=
public abstract class Code {
    
    // 序列化
    public abstract String serialize();
    
    // 反序列化
    public abstract TreeNode deserialize();
    
}
```

* 反序列 String，使用前序走訪範例：`"5, null, null, null, 7, 6, null"`
    
    > ![](https://i.imgur.com/SCYcBrI.png)

:::success
* 序列化 ?

    二元樹是一個二維的平面結構，而序列化後的字串是一個線性一維結構。所以 **序列化就是 ++將維度降為一維++**，**++重點仍是二元樹的尋訪++ !!**
:::

:::danger
* 反序列化要點

    **要反序列化必須先建立 root 節點**
:::

### 前序走訪 preorder

> **前序走訪從 左子樹的末端結點開始**

使用以下二元樹

> ![](https://i.imgur.com/rhpWWQN.png)

* **Serialize 序列化：**

    1. 套用框架並使用 **LinkedList** 實現
        ```java=
        // 序列化

        private final LinkedList<Integer> valList = new LinkedList<>();

        public void traverse_List(TreeNode root) {
            if(root == null) {
                valList.addLast(-1);
                return;
            }

            valList.addLast(root.val);

            traverse_List(root.left);
            traverse_List(root.right);
        }

        public static void main(String[] args) {
            OrderBehind orderBehind = new OrderBehind();


            TreeNode leftTree = new TreeNode(2, null, new TreeNode(4));
            TreeNode rightTree = new TreeNode(3);
            TreeNode tree = new TreeNode(1, leftTree, rightTree);

            orderBehind.traverse_List(tree);

            System.out.println(orderBehind.valList);
        }
        ```
        > ![](https://i.imgur.com/W05ADoR.png)

    2. 套用框架，使用 **StringBuilder** 串接
        ```java=
        // 序列化

        public void traverse_String(TreeNode root) {
                if(root == null) {
                    stringBuilder.append(NULL).append(SEP);
                    return;
                }

                stringBuilder.append(root.val).append(SEP);

                traverse_String(root.left);
                traverse_String(root.right);
            }

            public static void main(String[] args) {
                OrderBehind orderBehind = new OrderBehind();


                TreeNode leftTree = new TreeNode(2, null, new TreeNode(4));
                TreeNode rightTree = new TreeNode(3);
                TreeNode tree = new TreeNode(1, leftTree, rightTree);

                orderBehind.traverse_String(tree);

                System.out.println(orderBehind.stringBuilder);
            }
        ```
        > ![](https://i.imgur.com/4alc3wP.png)

* **Deserialize 反序列化：**

    ```java=
    // 反序列化

    private static final String SEP = ",";
    private static final String NULL = "null";

    public TreeNode deserialize(String nodes) {
        LinkedList<String> list = new LinkedList<>();
        for(String item : nodes.split(SEP)) {
            list.addLast(item);
        }
        return _deserialize(list);
    }

    private TreeNode _deserialize(LinkedList<String> list) {
        if(list.isEmpty()) {
            return null;
        }

        // 取出當前最前面的元素，代表了 root (僅限於前序)
        String first = list.removeFirst();
        // NULL 代表到末端節點了
        if(first.equals(NULL)) {
            return null;
        }
        
        TreeNode root = new TreeNode(Integer.parseInt(first));

        root.left = _deserialize(list);
        root.right = _deserialize(list);

        return root;
    }
    ```
    
### 後序走訪 postorder

> **後序走訪 先走訪所有結點，才輪到父節點**

* **Serialize 序列化**：序列化的方式也很簡單，套用模板後將序列化的方式寫在後續走訪的位置

    ```java=
    public class PostOrder {

        private static final String SEP = ",";
        private static final String NULL = "null";
        private final StringBuilder sb = new StringBuilder();

        void serialize(TreeNode root) {
            if(root == null) {
                sb.append(NULL).append(SEP);
                return;
            }

            serialize(root.left);

            serialize(root.right);

            sb.append(root.val).append(SEP);

        }

        public static void main(String[] args) {
            PostOrder postOrder = new PostOrder();

            TreeNode leftTree = new TreeNode(2, null, new TreeNode(4));
            TreeNode rightTree = new TreeNode(3);
            TreeNode tree = new TreeNode(1, leftTree, rightTree);

            postOrder.serialize(tree);
            String s = postOrder.sb.toString();
            System.out.println(s);
        }

    }
    ```
    > ![](https://i.imgur.com/3OCeTb6.png)

* **Deserialize 反序列化**：**這裡要特別注意，由於序列化時是使用 ++後序走訪++，所以在反序列化時，有以下特點**
    1. **root 節點在尾端，需 ==從尾端取值==**
    
    2. **由於從尾端開始取值，所以反序列化必須從 ==右到左==**
 
    ```java=
    // Deserialize

    public TreeNode deserialize(String data) {
        LinkedList<String> list = new LinkedList<>();
        for (String item : data.split(SEP)) {
            list.addLast(item);
        }
        return _deserialize(list);
    }

    private TreeNode _deserialize(LinkedList<String> list) {
        if(list.isEmpty()) {
            return null;
        }

        // 從最後一個開始取值 !
        String s = list.removeLast();
        if(NULL.equals(s)) {
            return null;
        }

        TreeNode root = new TreeNode(Integer.parseInt(s));

        // 先右再左 !
        root.right = _deserialize(list);
        root.left = _deserialize(list);

        return root;
    }

    public static void main(String[] args) {
        PostOrder postOrder = new PostOrder();

        TreeNode leftTree = new TreeNode(2, null, new TreeNode(4));
        TreeNode rightTree = new TreeNode(3);
        TreeNode tree = new TreeNode(1, leftTree, rightTree);

        postOrder.serialize(tree);
        String s = postOrder.sb.toString();
        System.out.println(s);

        TreeNode deserialize = postOrder.deserialize(s);
    }
    ```

### 中序走訪 inorder

* 中序走訪可以序列化，但是 **無法反序列化**，這是**因為 root 節點不在頭也不在尾，而是在中間，==無法確立 root 具體位置==** !


* **Serialize 序列化**：

    ```java=
    public class MiddleOrder {

        private static final String SEP = ",";
        private static final String NULL = "null";
        private final StringBuilder sb = new StringBuilder();

        public void serialize(TreeNode root) {
            if(root == null) {
                sb.append(NULL).append(SEP);
                return;
            }

            serialize(root.left);

            sb.append(root.val).append(SEP);

            serialize(root.right);
        }

        public static void main(String[] args) {
            MiddleOrder middleOrder = new MiddleOrder();

            TreeNode leftTree = new TreeNode(2, null, new TreeNode(4));
            TreeNode rightTree = new TreeNode(3);
            TreeNode tree = new TreeNode(1, leftTree, rightTree);

            middleOrder.serialize(tree);
            String s = middleOrder.sb.toString();
            System.out.println(s);
        }

    }
    ```
    > ![](https://i.imgur.com/SJvjQsm.png)



## Appendix & FAQ

:::info
:::

###### tags: `資料結構`
