[二叉樹 binary tree] 是一種非線性數據結構，代表著祖先與後代之間的派生關係，體現著” 一分為二 “的分治邏輯。
二叉樹的基本單元是節點，每個節點有：** 值、[左子節點 left-child node]引用、[右子節點 right-child node]** 引用。
class TreeNode {
int val;
TreeNode? left;
TreeNode? right;
TreeNode(int x) => val = x;
}
在二叉樹中，除葉節點外，其他所有節點都包含子節點和非空子樹(子節點及其以下節點形成的樹)。
二叉樹的常見術語#
- [根節點 root node]: 頂層節點，沒有父節點。
- [葉節點 leaf node]: 沒有子節點的節點。
- [邊 edge]: 連接兩個節點的線段，即節點引用（指針）。
- 節點所在的 [層 level]: 從頂至底遞增，根節點所在層為 1。
- 節點的 [度 degree]: 節點的子節點的數量。在二叉樹中，度的取值範圍是 0、1、2。
- 二叉樹的 [高度 height]: 從根節點到最遠葉節點所經過的邊的數量。
- 節點的 [深度 depth]: 從根節點到該節點所經過的邊的數量。
- 節點的 [高度 height]: 從最遠葉節點到該節點所經過的邊的數量。
💡 請注意，通常將 “高度” 和 “深度” 定義為 “走過邊的數量”。
常見二叉樹類型#
1. [完美 (滿) 二叉樹 perfect binary tree]#
除了最底層外，其餘所有層的節點都被完全填滿。
2. [完全二叉樹 complete binary tree]#
只有最底層的節點未被填滿，且最底層節點盡量靠左填充。
3. [完滿二叉樹 full binary tree]#
除了葉節點之外，其餘所有節點都有兩個子節點。
4. [平衡二叉樹 balanced binary tree]#
任意節點的左子樹和右子樹的高度之差的絕對值不超過 1。
二叉樹遍歷#
[層序遍歷 level-order traversal]#
[層序遍歷 level-order traversal] 從頂部到底部逐層遍歷二叉樹，並在每一層按照從左到右的順序訪問節點。
層序遍歷本質上屬於 [廣度優先遍歷 breadth-first traversal]，體現了” 一圈一圈向外擴展 “的逐層遍歷方式。
廣度優先遍歷通常借助” 隊列” 來實現。
/* 層序遍歷 */
List<int> LevelOrder(TreeNode root) {
// 初始化隊列，加入根節點
Queue<TreeNode> queue = new();
queue.Enqueue(root);
// 初始化一個列表，用於保存遍歷序列
List<int> list = new();
while (queue.Count != 0) {
TreeNode node = queue.Dequeue(); // 隊列出隊
list.Add(node.val); // 保存節點值
if (node.left != null)
queue.Enqueue(node.left); // 左子節點入隊
if (node.right != null)
queue.Enqueue(node.right); // 右子節點入隊
}
return list;
}
前序、中序、後序遍歷#
前序、中序、後序遍歷都屬於 [深度優先遍歷 depth-first traversal]，它體現了一種”先走到頭，再回溯繼續“的遍歷方式。
深度優先遍歷就像是繞著整個二叉樹的外圍” 走 “一圈，在每個節點都會遇到三個位置，分別對應前序遍歷、中序遍歷和後序遍歷。
深度優先遍歷通常基於遞歸實現。
/* **前序**遍歷 */
void PreOrder(TreeNode? root) {
if (root == null) return;
// 訪問優先級：**根**節點 -> **左**子樹 -> **右**子樹
list.Add(root.val);
PreOrder(root.left);
PreOrder(root.right);
}
/* **中序**遍歷 */
void InOrder(TreeNode? root) {
if (root == null) return;
// 訪問優先級：**左**子樹 -> **根**節點 -> **右**子樹
InOrder(root.left);
list.Add(root.val);
InOrder(root.right);
}
/* **後序**遍歷 */
void PostOrder(TreeNode? root) {
if (root == null) return;
// 訪問優先級：**左**子樹 -> **右**子樹 -> **根**節點
PostOrder(root.left);
PostOrder(root.right);
list.Add(root.val);
}
記憶口訣：
前序：根左右，中序：左根右，後序：左右根。