---
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);
}
}
```
建構出的二元樹圖如下
> 
* 現在將上面二元樹上的 **每個節點 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());
}
}
```
> 
### 基礎控制 - 比較兩個樹
* 現在來比較兩個 Tree 是否相同，**同樣注意這裡的 base case** (**換位思考一下最底端，也就是末端時，你要如何處理方法的返回**)
1. 兩個 root 都為 null，返回 true
> 
2. 兩個 root 只有其中一個為 null，這就不相符，返回 false
> 
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);
}
}
```
> 
## 二元樹 - 規則
> 二元樹的排序是有規則的，按照規則來進行排序
1. **右子樹任意節點 (Node)，要大於等於 ++左子樹++的 ==所有== 節點**
2. **左子樹任意節點 (Node)，要小於等於 ++右子樹++的 ==所有== 節點**
### 二元樹 vs. Heap 規則
* Heap 也是使用二元分治法，不過它的規則 與 二元樹不同，**Heap 不是一個合法的二元樹**
* 二元樹 vs. Heap 規則不同點
1. **入隊方式**
* Heap：**從末端 Tail 入隊**，之後針對新數值進行 swim 上浮作業
* 二元樹：**從起始端 Header 入隊**，比較當前節點，**小於放置左側子樹、大於放置右測子樹** (最終可以達到左子樹全部節點都比右子樹任一節點小)
> 
2. **樹形狀**
* Heap：限制必須是 **完全 or 滿二元樹** (一定會有左節點才會有右節點)
* 二元樹：沒有限制，可以傾斜，不規則
> 
3. **Child Node 節點規則**
* Heap：不可以比 Parent 節點大
* 二元樹：不可以比 Parent 節點大、**並且左子樹的所有節點都小於右子樹的任一節點** (Heap 無法達到這個規則)
> 
### 判斷 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 必須比較子樹的 **所有節點 (這個所有就是重點!)，並符合條件**; 像是以圖就可以演示這個問題
> 
```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 應該不合法 !
> 
上述測試的問題點：**根結點 10 應該小於全部右子樹的節點 (這樣 9 就不符合)**，**++應該返回 false 才對++**
> 
### 判斷 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 兩個 !
:::
> 
```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);
}
```
> 
### BST 尋找指定數 - 遞迴
BST 二元搜尋，以下我們使用這棵樹
> 
* 由於使用遞迴，所以重點仍先放在 ^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);
}
```
> 
### BST 尋找指定數 - 非遞迴 (迭代)
BST 二元搜尋，以下我們使用這棵樹
> 
* 除了上面的遞迴方法以外，我們也可以使用非遞迴的方式搜尋該二元樹
```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);
}
```
> 
### BST 插入一個數
以下我們使用這棵樹
> 
* **資料結構的操作，無非是尋訪 (找)、存取 (改)**；如果要改就是先進行 `找`，找到目標節點後，再進行 `改` (也就是插入)
:::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);
}
```
> 
:::info
* 以不同順序插入二元樹會對於最終二元樹圖形的結果有影響
如果以遞增順序插入，則效率會最差，會轉為一個 偏移傾斜二元樹；這時找尋一個數值就會耗費 O(N) 的時間
> 
:::
### 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，就是斷開節點
}
```
> 
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; // 同上 `手動交換`
}
```
> 
3. **刪除 Node 有兩個子樹（難）**：**為了不破壞二元樹的規則**，以下有兩種方案 (都以刪除 `2` 這個 Node 為目標)；**找左最大、找右最小，使用其中一個即可**
* **左子樹：必須找到 ++左子樹中 ==最大==++ 的節點來交換**
> 2 跟 1 交換
>
> 
```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 交換
>
> 
```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` 這個節點
> 
```java=
public static void main(String[] args) {
TreeNode baseTreeNode = TreeNode.getBaseTreeNode();
DeleteNode deleteNode = new DeleteNode();
TreeNode result = deleteNode.deleteNode(baseTreeNode, 5);
// 前序走訪
TreeNode.traverse(result);
}
```
> 
:::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);
}
}
```
> 
:::
## 二元樹分類
### 完全二元樹
* 每一層都緊靠左邊，如果有其中一層 **無緊靠左側 (若沒有緊靠左側，就不是完整二元樹)**，則不是完全二元樹
> 類似於 Heap 的規則
> 
:::success
* 英文的完全二元樹是 **Complete Binary Tree**
:::
### 滿二元樹
* 每一層的元素都是滿的
> 
:::success
* 英文的滿二元樹是 **Perfect Binary Tree**
:::
## Node 數量
### 普通二元樹 - Node 數量
計算以下二元樹
> 
```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
:::
**--實作結果--**
> 
### 滿二元樹 - Node 數量
計算以下二元樹
> 
* 滿二元樹可以跳脫框架進行更快速的計算，規則如下：**滿二元樹總結點數量為：==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);
}
}
```
**--實作結果--**
> 
### 完全二元樹 - Node 數量
計算以下二元樹
> 
* **完全二元樹，其實又跟滿二元樹相同。所以完全二元樹 = 普通二元樹 + 滿二元樹的測量**
```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);
}
}
```
**--實作--**
> 
* **BIG O 大小：這種寫法的重點是從根結點開始的左、右子樹，只有一個會真正往下去做，另一個則會執行滿二元樹**
1. 遞迴演算法對於樹的高度為 `O(logN)`
2. 每次遞迴所花費的時間為 while 計算高度，計算高度的時間為 `O(2 * logN)`
3. 最終使用時間為 `O(2 * logN logN)`
> 
## 序列化 & 反序列化 BST
```java=
public abstract class Code {
// 序列化
public abstract String serialize();
// 反序列化
public abstract TreeNode deserialize();
}
```
* 反序列 String，使用前序走訪範例：`"5, null, null, null, 7, 6, null"`
> 
:::success
* 序列化 ?
二元樹是一個二維的平面結構，而序列化後的字串是一個線性一維結構。所以 **序列化就是 ++將維度降為一維++**，**++重點仍是二元樹的尋訪++ !!**
:::
:::danger
* 反序列化要點
**要反序列化必須先建立 root 節點**
:::
### 前序走訪 preorder
> **前序走訪從 左子樹的末端結點開始**
使用以下二元樹
> 
* **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);
}
```
> 
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);
}
```
> 
* **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);
}
}
```
> 
* **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);
}
}
```
> 
## Appendix & FAQ
:::info
:::
###### tags: `資料結構`
Sign in with Wallet
Connect another wallet