引言

二叉樹（Binary Tree）作為算法領域的核心數據結構，在搜索、排序、數據庫索引、編譯器語法樹構建等眾多場景中都有著廣泛應用。無論是初學者夯實算法基礎，還是求職者備戰技術面試，掌握二叉樹相關算法都是不可或缺的。本文將通過 Java 語言，從基礎概念、核心遍歷算法出發，深入解析高頻面試題，并分享進階技巧，幫助開發者構建系統的二叉樹算法知識體系。

一、二叉樹基礎概念

1.1 節點定義

在 Java 中，二叉樹的節點通常定義如下：

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

上述代碼定義了TreeNode類，每個節點包含一個值val，以及指向左子節點left和右子節點right的引用，同時提供了不同的構造函數方便節點創建。

1.2 二叉樹類型

類型	特征	應用場景
滿二叉樹	所有非葉子節點都有兩個子節點，每一層節點數都達到最大值	構建完美平衡結構，用于理論研究或特定算法場景
完全二叉樹	除最后一層外全滿，最后一層左對齊，可通過數組高效存儲	堆結構實現，如優先隊列
二叉搜索樹 (BST)	左子樹所有節點值 < 根 < 右子樹，中序遍歷可得到有序序列	快速查找、插入和刪除操作，用于實現字典、符號表
平衡二叉樹 (AVL)	任意節點左右子樹高度差≤1，通過旋轉操作保持平衡	數據庫索引、文件系統目錄結構，保證查找效率穩定
紅黑樹	自平衡二叉搜索樹，滿足著色規則（節點為紅或黑，根節點為黑等）	Java 中的TreeMap和TreeSet實現，在動態數據集合中有較好性能

二、核心遍歷算法

2.1 遞歸遍歷

遞歸遍歷是實現二叉樹遍歷的直觀方式，基于深度優先搜索（DFS）思想：

// 前序遍歷：根 -> 左 -> 右
void preOrder(TreeNode root) {if (root == null) return;System.out.print(root.val + " ");preOrder(root.left);preOrder(root.right);
}// 中序遍歷：左 -> 根 -> 右（BST得到有序序列）
void inOrder(TreeNode root) {if (root == null) return;inOrder(root.left);System.out.print(root.val + " ");inOrder(root.right);
}// 后序遍歷：左 -> 右 -> 根
void postOrder(TreeNode root) {if (root == null) return;postOrder(root.left);postOrder(root.right);System.out.print(root.val + " ");
}

遞歸遍歷簡潔易懂，但當樹的深度較大時，可能會導致棧溢出問題。

2.2 迭代遍歷（棧實現）

使用棧可以將遞歸過程轉化為迭代過程，避免棧溢出：

// 前序遍歷（棧實現）
List<Integer> preOrderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();Deque<TreeNode> stack = new LinkedList<>();TreeNode cur = root;while (cur != null || !stack.isEmpty()) {while (cur != null) {res.add(cur.val);  // 訪問根節點stack.push(cur);cur = cur.left;  // 深入左子樹}cur = stack.pop();cur = cur.right;  // 轉向右子樹}return res;
}// 中序遍歷（棧實現）
List<Integer> inOrderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();Deque<TreeNode> stack = new LinkedList<>();TreeNode cur = root;while (cur != null ||!stack.isEmpty()) {while (cur != null) {stack.push(cur);cur = cur.left;}cur = stack.pop();res.add(cur.val);cur = cur.right;}return res;
}// 后序遍歷（棧實現）
List<Integer> postOrderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();Deque<TreeNode> stack1 = new LinkedList<>();Deque<Integer> stack2 = new LinkedList<>();TreeNode cur = root;while (cur != null ||!stack1.isEmpty()) {while (cur != null) {stack1.push(cur);stack2.push(1);cur = cur.right;}cur = stack1.pop();if (stack2.pop() == 1) {stack1.push(cur);stack2.push(2);cur = cur.left;} else {res.add(cur.val);}}return res;
}

2.3 層次遍歷（隊列實現）

層次遍歷基于廣度優先搜索（BFS），使用隊列來實現：

List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> res = new ArrayList<>();if (root == null) return res;Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {int levelSize = queue.size();List<Integer> level = new ArrayList<>();for (int i = 0; i < levelSize; i++) {TreeNode node = queue.poll();level.add(node.val);if (node.left != null) queue.offer(node.left);if (node.right != null) queue.offer(node.right);}res.add(level);}return res;
}

層次遍歷常用于獲取二叉樹的每一層節點值，或判斷樹的某些性質，如是否為完全二叉樹。

三、高頻面試題精講

3.1 二叉樹的最大深度（LeetCode 104）

題目描述：給定一個二叉樹，找出其最大深度。

int maxDepth(TreeNode root) {if (root == null) return 0;return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}

解題思路：使用遞歸方法，分別計算左子樹和右子樹的最大深度，取較大值再加上根節點這一層。

3.2 對稱二叉樹（LeetCode 101）

題目描述：給定一個二叉樹，檢查它是否是鏡像對稱的。

boolean isSymmetric(TreeNode root) {return root == null || checkSymmetric(root.left, root.right);
}boolean checkSymmetric(TreeNode left, TreeNode right) {if (left == null && right == null) return true;if (left == null || right == null) return false;return left.val == right.val && checkSymmetric(left.left, right.right) && checkSymmetric(left.right, right.left);
}

解題思路：遞歸比較左子樹的左節點和右子樹的右節點，以及左子樹的右節點和右子樹的左節點。

3.3 二叉樹的序列化（LeetCode 297）

題目描述：設計一個算法來序列化和反序列化二叉樹。

public String serialize(TreeNode root) {if (root == null) return "null";return root.val + "," + serialize(root.left) + "," + serialize(root.right);
}public TreeNode deserialize(String data) {Queue<String> queue = new LinkedList<>(Arrays.asList(data.split(",")));return buildTree(queue);
}private TreeNode buildTree(Queue<String> queue) {String val = queue.poll();if ("null".equals(val)) return null;TreeNode node = new TreeNode(Integer.parseInt(val));node.left = buildTree(queue);node.right = buildTree(queue);return node;
}

解題思路：序列化時使用前序遍歷將二叉樹轉化為字符串，反序列化時根據字符串重新構建二叉樹。

四、進階算法技巧

4.1 Morris 遍歷

Morris 遍歷是一種實現 O (1) 空間復雜度中序遍歷的方法，其核心思想是利用葉子節點的空指針來保存前驅節點信息，從而避免使用棧。該算法通過在遍歷過程中構建臨時的線索二叉樹，實現對樹的高效遍歷，具體步驟較為復雜，但在對空間要求苛刻的場景下非常有用。

4.2 二叉搜索樹驗證（LeetCode 98）

題目描述：給定一個二叉樹，判斷其是否是一個有效的二叉搜索樹。

boolean isValidBST(TreeNode root) {return validate(root, Long.MIN_VALUE, Long.MAX_VALUE);
}boolean validate(TreeNode node, long lower, long upper) {if (node == null) return true;if (node.val <= lower || node.val >= upper) return false;return validate(node.left, lower, node.val) && validate(node.right, node.val, upper);
}

解題思路：遞歸驗證每個節點的值是否在其對應的取值范圍內，左子樹所有節點值小于根節點，右子樹所有節點值大于根節點。

五、注意事項

1. 空指針處理：在操作二叉樹節點前，始終要檢查節點是否為null，避免出現NullPointerException。
2. 遞歸終止條件：明確遞歸的退出條件，防止無限遞歸導致棧溢出。
3. 棧溢出風險：當二叉樹深度過大時，遞歸遍歷可能會耗盡棧空間，此時應優先使用迭代法。
4. 狀態保存：在使用回溯算法解決二叉樹問題時，要及時恢復現場，避免影響后續操作。

六、性能優化方向

1. 記憶化搜索：對于一些需要重復計算的問題，如計算二叉樹中滿足特定條件的路徑和，使用記憶化搜索可以避免重復計算，提高效率。
2. 尾遞歸優化：雖然 Java 目前對尾遞歸優化支持有限，但在一些特定編譯器或運行環境中，可以利用尾遞歸優化來減少棧空間的占用。
3. 迭代替代遞歸：將遞歸算法轉化為迭代算法，通過顯式使用棧或隊列，可以有效降低空間復雜度。
4. 剪枝策略：在解決一些搜索問題時，提前判斷某些分支是否無效，及時終止搜索，減少不必要的計算。

結語

掌握二叉樹算法的關鍵在于理解樹形結構的遞歸本質，并熟練運用各種遍歷框架來解決各類問題。從基礎的遍歷操作到復雜的算法應用，都需要通過大量的練習來加深理解。建議讀者從本文的基礎代碼和題目入手，逐步挑戰 LeetCode 上更多經典題目，在實踐中實現從量變到質變的提升。

如果在學習過程中有任何疑問，歡迎在評論區留言交流，也希望大家分享自己的學習心得和技巧，共同進步！