Java二叉樹遍歷與遞歸詳解(從入門到精通)
更新時(shí)間：2026年03月16日 10:12:20 作者：識(shí)君啊
二叉樹是一棵空樹,或者是一棵由一個(gè)根節(jié)點(diǎn)和兩棵互不相交的,分別稱作根的左子樹和右子樹組成的非空樹,這篇文章主要介紹了Java二叉樹遍歷與遞歸的相關(guān)資料,文中通過代碼介紹的非常詳細(xì),需要的朋友可以參考下
二叉樹不難，就是"遞歸+隊(duì)列"
一、什么是二叉樹？
1.1 生活中的二叉樹
想象一個(gè)家族族譜：
爺爺
/ \
爸爸 叔叔
/ \ / \
我 弟弟 堂哥 堂妹
這就是一棵二叉樹：
- 爺爺是根節(jié)點(diǎn)（最頂層）
- 爸爸和叔叔是爺爺?shù)淖庸?jié)點(diǎn)
- 我和弟弟是爸爸的子節(jié)點(diǎn)
- 每個(gè)節(jié)點(diǎn)最多有2個(gè)子節(jié)點(diǎn)（左孩子、右孩子）
1.2 二叉樹的定義
二叉樹： 每個(gè)節(jié)點(diǎn)最多有兩個(gè)子節(jié)點(diǎn)的樹形結(jié)構(gòu)
LeetCode標(biāo)準(zhǔn)節(jié)點(diǎn)結(jié)構(gòu)：
/**
* Definition for a binary tree node.
* 這是LeetCode所有二叉樹題目使用的標(biāo)準(zhǔn)結(jié)構(gòu)
*/
public class TreeNode {
int val; // 節(jié)點(diǎn)存儲(chǔ)的值
TreeNode left; // 指向左子節(jié)點(diǎn)的引用
TreeNode right; // 指向右子節(jié)點(diǎn)的引用
// 構(gòu)造函數(shù)1：只傳入值，左右子節(jié)點(diǎn)默認(rèn)為null
TreeNode() {}
// 構(gòu)造函數(shù)2：傳入值并初始化
TreeNode(int val) {
this.val = val;
}
// 構(gòu)造函數(shù)3：傳入值和左右子節(jié)點(diǎn)
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
舉例：構(gòu)建一棵樹
1
/ \
2 3
/ \
4 5
方式1：逐個(gè)創(chuàng)建節(jié)點(diǎn)
TreeNode root = new TreeNode(1); root.left = new TreeNode(2); root.right = new TreeNode(3); root.left.left = new TreeNode(4); root.left.right = new TreeNode(5);
方式2：使用完整構(gòu)造函數(shù)
TreeNode root = new TreeNode(1,
new TreeNode(2,
new TreeNode(4),
new TreeNode(5)
),
new TreeNode(3)
);
1.3 二叉樹的基本概念
- 節(jié)點(diǎn)： 樹中的每個(gè)元素
- 根節(jié)點(diǎn)： 最頂層的節(jié)點(diǎn)（如上圖的1）
- 葉子節(jié)點(diǎn)： 沒有子節(jié)點(diǎn)的節(jié)點(diǎn)（如上圖的3、4、5）
- 深度： 從根節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的層數(shù)（根節(jié)點(diǎn)深度為0）
- 高度： 從當(dāng)前節(jié)點(diǎn)到葉子節(jié)點(diǎn)的最大層數(shù)
示例：
1 ← 根節(jié)點(diǎn)，深度0，高度2
/ \
2 3 ← 深度1，高度1（節(jié)點(diǎn)2）和0（節(jié)點(diǎn)3）
/ \
4 5 ← 葉子節(jié)點(diǎn)，深度2，高度0
1.4 特殊的二叉樹
滿二叉樹： 每層節(jié)點(diǎn)都是滿的，所有葉子節(jié)點(diǎn)在同一層
1
/ \
2 3
/ \ / \
4 5 6 7
特點(diǎn)：節(jié)點(diǎn)數(shù) = 2^h - 1（h是高度）
完全二叉樹： 除了最后一層，其他層都是滿的，且最后一層從左到右連續(xù)
1
/ \
2 3
/ \
4 5
特點(diǎn)：適合用數(shù)組存儲(chǔ)，堆就是完全二叉樹
二叉搜索樹（BST）： 左子樹所有節(jié)點(diǎn) < 根節(jié)點(diǎn) < 右子樹所有節(jié)點(diǎn)
5
/ \
3 7
/ \ / \
1 4 6 9
特點(diǎn)：中序遍歷是升序，查找效率O(log n)
平衡二叉樹（AVL樹）： 任意節(jié)點(diǎn)的左右子樹高度差不超過1
5
/ \
3 7
/ / \
1 6 9
特點(diǎn)：保證樹的高度平衡，查找/插入/刪除都是O(log n)
平衡二叉搜索樹： 同時(shí)滿足BST和平衡樹的性質(zhì)
5
/ \
3 7
/ \ / \
2 4 6 8
特點(diǎn)：結(jié)合了BST的有序性和平衡樹的高效性，常見實(shí)現(xiàn)有AVL樹、紅黑樹
對比總結(jié)：
| 類型 | 特點(diǎn) | 應(yīng)用場景 |
|---|---|---|
| 滿二叉樹 | 每層都滿 | 理論模型 |
| 完全二叉樹 | 最后一層從左到右連續(xù) | 堆、優(yōu)先隊(duì)列 |
| 二叉搜索樹 | 左<根<右 | 查找、排序 |
| 平衡二叉樹 | 高度差≤1 | 保證性能 |
| 平衡二叉搜索樹 | BST+平衡 | 數(shù)據(jù)庫索引、TreeMap |
二、二叉樹的遍歷方式
遍歷就是"按某種順序訪問所有節(jié)點(diǎn)"。
2.1 兩大類遍歷方式
深度優(yōu)先遍歷（DFS）： 先往深處走，走到底再回頭
- 前序遍歷（根-左-右）
- 中序遍歷（左-根-右）
- 后序遍歷（左-右-根）
廣度優(yōu)先遍歷（BFS）： 一層一層地訪問
- 層序遍歷（從上到下，從左到右）
2.2 遍歷順序?qū)Ρ?/h3>
以這棵樹為例：
1
/ \
2 3
/ \
4 5
- 前序遍歷： 1 → 2 → 4 → 5 → 3（根-左-右）
- 中序遍歷： 4 → 2 → 5 → 1 → 3（左-根-右）
- 后序遍歷： 4 → 5 → 2 → 3 → 1（左-右-根）
- 層序遍歷： 1 → 2 → 3 → 4 → 5（一層一層）
三、深度優(yōu)先遍歷（DFS）
3.1 前序遍歷（根-左-右）
順序： 先訪問根節(jié)點(diǎn)，再訪問左子樹，最后訪問右子樹
遞歸實(shí)現(xiàn)（詳細(xì)注釋版）：
/**
* 前序遍歷：根-左-右
* @param root 當(dāng)前節(jié)點(diǎn)
*/
public void preorder(TreeNode root) {
// 遞歸終止條件：節(jié)點(diǎn)為空，直接返回
if (root == null) return;
// 1. 訪問根節(jié)點(diǎn)（前序的"前"就是指這里）
System.out.print(root.val + " ");
// 2. 遞歸遍歷左子樹
preorder(root.left);
// 3. 遞歸遍歷右子樹
preorder(root.right);
}
// 調(diào)用示例
public static void main(String[] args) {
TreeNode root = new TreeNode(1,
new TreeNode(2,
new TreeNode(4),
new TreeNode(5)
),
new TreeNode(3)
);
System.out.print("前序遍歷結(jié)果：");
preorder(root); // 輸出：1 2 4 5 3
}
執(zhí)行過程詳解：
樹：
1
/ \
2 3
/ \
4 5
執(zhí)行流程（帶調(diào)用棧）：
preorder(1)
├─ 輸出1
├─ preorder(2)
│ ├─ 輸出2
│ ├─ preorder(4)
│ │ ├─ 輸出4
│ │ ├─ preorder(null) → 返回
│ │ └─ preorder(null) → 返回
│ └─ preorder(5)
│ ├─ 輸出5
│ ├─ preorder(null) → 返回
│ └─ preorder(null) → 返回
└─ preorder(3)
├─ 輸出3
├─ preorder(null) → 返回
└─ preorder(null) → 返回
最終輸出：1 2 4 5 3
迭代實(shí)現(xiàn)（用棧）：
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) return result;
// 用棧模擬遞歸
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
// 彈出棧頂節(jié)點(diǎn)并訪問
TreeNode node = stack.pop();
result.add(node.val);
// 先壓右子樹，再壓左子樹（棧是后進(jìn)先出，所以先壓右邊）
if (node.right != null) stack.push(node.right);
if (node.left != null) stack.push(node.left);
}
return result;
}
3.2 中序遍歷（左-根-右）
順序： 先訪問左子樹，再訪問根節(jié)點(diǎn)，最后訪問右子樹
遞歸實(shí)現(xiàn)（詳細(xì)注釋版）：
/**
* 中序遍歷：左-根-右
* @param root 當(dāng)前節(jié)點(diǎn)
*/
public void inorder(TreeNode root) {
// 遞歸終止條件
if (root == null) return;
// 1. 先遞歸遍歷左子樹
inorder(root.left);
// 2. 訪問根節(jié)點(diǎn)（中序的"中"就是指這里，在中間訪問）
System.out.print(root.val + " ");
// 3. 最后遞歸遍歷右子樹
inorder(root.right);
}
// 調(diào)用示例
public static void main(String[] args) {
TreeNode root = new TreeNode(1,
new TreeNode(2,
new TreeNode(4),
new TreeNode(5)
),
new TreeNode(3)
);
System.out.print("中序遍歷結(jié)果：");
inorder(root); // 輸出：4 2 5 1 3
}
執(zhí)行過程詳解：
樹：
1
/ \
2 3
/ \
4 5
執(zhí)行流程（帶調(diào)用棧）：
inorder(1)
├─ inorder(2)
│ ├─ inorder(4)
│ │ ├─ inorder(null) → 返回
│ │ ├─ 輸出4
│ │ └─ inorder(null) → 返回
│ ├─ 輸出2
│ └─ inorder(5)
│ ├─ inorder(null) → 返回
│ ├─ 輸出5
│ └─ inorder(null) → 返回
├─ 輸出1
└─ inorder(3)
├─ inorder(null) → 返回
├─ 輸出3
└─ inorder(null) → 返回
最終輸出：4 2 5 1 3
迭代實(shí)現(xiàn)（用棧）：
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode curr = root;
while (curr != null || !stack.isEmpty()) {
// 一直往左走，把所有左節(jié)點(diǎn)壓棧
while (curr != null) {
stack.push(curr);
curr = curr.left;
}
// 彈出棧頂節(jié)點(diǎn)，訪問
curr = stack.pop();
result.add(curr.val);
// 轉(zhuǎn)向右子樹
curr = curr.right;
}
return result;
}
3.3 后序遍歷（左-右-根）
順序： 先訪問左子樹，再訪問右子樹，最后訪問根節(jié)點(diǎn)
遞歸實(shí)現(xiàn)（詳細(xì)注釋版）：
/**
* 后序遍歷：左-右-根
* @param root 當(dāng)前節(jié)點(diǎn)
*/
public void postorder(TreeNode root) {
// 遞歸終止條件
if (root == null) return;
// 1. 先遞歸遍歷左子樹
postorder(root.left);
// 2. 再遞歸遍歷右子樹
postorder(root.right);
// 3. 最后訪問根節(jié)點(diǎn)（后序的"后"就是指這里，最后訪問）
System.out.print(root.val + " ");
}
// 調(diào)用示例
public static void main(String[] args) {
TreeNode root = new TreeNode(1,
new TreeNode(2,
new TreeNode(4),
new TreeNode(5)
),
new TreeNode(3)
);
System.out.print("后序遍歷結(jié)果：");
postorder(root); // 輸出：4 5 2 3 1
}
執(zhí)行過程詳解：
樹：
1
/ \
2 3
/ \
4 5
執(zhí)行流程（帶調(diào)用棧）：
postorder(1)
├─ postorder(2)
│ ├─ postorder(4)
│ │ ├─ postorder(null) → 返回
│ │ ├─ postorder(null) → 返回
│ │ └─ 輸出4
│ ├─ postorder(5)
│ │ ├─ postorder(null) → 返回
│ │ ├─ postorder(null) → 返回
│ │ └─ 輸出5
│ └─ 輸出2
├─ postorder(3)
│ ├─ postorder(null) → 返回
│ ├─ postorder(null) → 返回
│ └─ 輸出3
└─ 輸出1
最終輸出：4 5 2 3 1
迭代實(shí)現(xiàn)（用棧）：
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) return result;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
result.add(0, node.val); // 插入到結(jié)果開頭
// 先壓左子樹，再壓右子樹
if (node.left != null) stack.push(node.left);
if (node.right != null) stack.push(node.right);
}
return result;
}
3.4 三種遍歷的對比
| 遍歷方式 | 順序 | 輸出位置 | 應(yīng)用場景 |
|---|---|---|---|
| 前序遍歷 | 根-左-右 | 進(jìn)入節(jié)點(diǎn)時(shí)輸出 | 復(fù)制樹、序列化 |
| 中序遍歷 | 左-根-右 | 左子樹遍歷完輸出 | BST排序輸出 |
| 后序遍歷 | 左-右-根 | 左右子樹都遍歷完輸出 | 刪除樹、計(jì)算高度 |
記憶技巧：
- 前序：根節(jié)點(diǎn)在前面（先輸出根）
- 中序：根節(jié)點(diǎn)在中間（左子樹輸出完再輸出根）
- 后序：根節(jié)點(diǎn)在后面（左右子樹都輸出完再輸出根）
四、廣度優(yōu)先遍歷（BFS）
4.1 層序遍歷
順序： 從上到下，從左到右，一層一層訪問
示例：
1
/ \
2 3
/ \
4 5
層序遍歷：1 → 2 → 3 → 4 → 5
實(shí)現(xiàn)（用隊(duì)列）：
public List<Integer> levelOrder(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) return result;
// 用隊(duì)列實(shí)現(xiàn)層序遍歷
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
// 彈出隊(duì)首節(jié)點(diǎn)并訪問
TreeNode node = queue.poll();
result.add(node.val);
// 先加左子節(jié)點(diǎn)，再加右子節(jié)點(diǎn)（隊(duì)列是先進(jìn)先出）
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
return result;
}
執(zhí)行過程：
初始：queue = [1] 第1輪： 彈出1，輸出1 加入2和3 queue = [2, 3] 第2輪： 彈出2，輸出2 加入4和5 queue = [3, 4, 5] 第3輪： 彈出3，輸出3 queue = [4, 5] 第4輪： 彈出4，輸出4 queue = [5] 第5輪： 彈出5，輸出5 queue = [] 結(jié)果：1 2 3 4 5
4.2 分層輸出（重要）
需求： 輸出每一層的節(jié)點(diǎn)
示例：
1
/ \
2 3
/ \
4 5
輸出：
[[1], [2,3], [4,5]]
實(shí)現(xiàn)：
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) return result;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size(); // 當(dāng)前層的節(jié)點(diǎn)數(shù)（關(guān)鍵?。?
List<Integer> level = new ArrayList<>();
// 遍歷當(dāng)前層的所有節(jié)點(diǎn)
for (int i = 0; i < size; 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);
}
result.add(level);
}
return result;
}
關(guān)鍵： int size = queue.size() 記錄當(dāng)前層的節(jié)點(diǎn)數(shù)
4.3 DFS vs BFS
| 對比項(xiàng) | DFS（深度優(yōu)先） | BFS（廣度優(yōu)先） |
|---|---|---|
| 數(shù)據(jù)結(jié)構(gòu) | 棧（或遞歸） | 隊(duì)列 |
| 遍歷方式 | 先往深處走 | 一層一層走 |
| 空間復(fù)雜度 | O(h)，h是樹高 | O(w)，w是最大寬度 |
| 應(yīng)用場景 | 路徑問題、樹的高度 | 最短路徑、層級(jí)問題 |
記憶技巧：
- DFS = 深（Deep）= 棧（Stack）= 遞歸
- BFS = 寬（Broad）= 隊(duì)列（Queue）= 層序
五、二叉樹的經(jīng)典問題
5.1 求二叉樹的最大深度（LeetCode 104）
題目： 給定一個(gè)二叉樹，找出其最大深度。
示例：
3
/ \
9 20
/ \
15 7
最大深度：3
思路： 樹的深度 = max(左子樹深度, 右子樹深度) + 1
遞歸實(shí)現(xiàn)：
public int maxDepth(TreeNode root) {
// 空節(jié)點(diǎn)深度為0
if (root == null) return 0;
// 遞歸計(jì)算左右子樹深度
int leftDepth = maxDepth(root.left);
int rightDepth = maxDepth(root.right);
// 當(dāng)前節(jié)點(diǎn)深度 = 左右子樹最大深度 + 1
return Math.max(leftDepth, rightDepth) + 1;
}
5.2 翻轉(zhuǎn)二叉樹（LeetCode 226）
題目： 翻轉(zhuǎn)一棵二叉樹。
遞歸實(shí)現(xiàn)：
public TreeNode invertTree(TreeNode root) {
if (root == null) return null;
// 交換左右子樹
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
// 遞歸翻轉(zhuǎn)左右子樹
invertTree(root.left);
invertTree(root.right);
return root;
}
5.3 對稱二叉樹（LeetCode 101）
題目： 判斷一棵二叉樹是否對稱。
遞歸實(shí)現(xiàn)：
public boolean isSymmetric(TreeNode root) {
if (root == null) return true;
return isMirror(root.left, root.right);
}
private boolean isMirror(TreeNode left, TreeNode right) {
if (left == null && right == null) return true;
if (left == null || right == null) return false;
if (left.val != right.val) return false;
return isMirror(left.left, right.right) &&
isMirror(left.right, right.left);
}
5.4 二叉樹的最近公共祖先（LeetCode 236）
遞歸實(shí)現(xiàn)：
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || root == p || root == q) {
return root;
}
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if (left != null && right != null) {
return root;
}
return left != null ? left : right;
}
5.5 二叉樹的右視圖（LeetCode 199）
BFS實(shí)現(xiàn)：
public List<Integer> rightSideView(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) return result;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
// 每層的最后一個(gè)節(jié)點(diǎn)
if (i == size - 1) {
result.add(node.val);
}
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
}
return result;
}
5.6 路徑總和（LeetCode 112）
遞歸實(shí)現(xiàn)：
public boolean hasPathSum(TreeNode root, int targetSum) {
if (root == null) return false;
// 葉子節(jié)點(diǎn)，判斷是否等于目標(biāo)和
if (root.left == null && root.right == null) {
return root.val == targetSum;
}
// 遞歸左右子樹，目標(biāo)和減去當(dāng)前節(jié)點(diǎn)值
return hasPathSum(root.left, targetSum - root.val) ||
hasPathSum(root.right, targetSum - root.val);
}
六、二叉搜索樹（BST）
6.1 什么是二叉搜索樹？
定義： 左子樹所有節(jié)點(diǎn) < 根節(jié)點(diǎn) < 右子樹所有節(jié)點(diǎn)
示例：
5
/ \
3 7
/ \ / \
1 4 6 9
特點(diǎn)： 中序遍歷BST，得到的是升序序列
中序遍歷： 1 → 3 → 4 → 5 → 6 → 7 → 9（升序）
6.2 驗(yàn)證二叉搜索樹（LeetCode 98）
遞歸實(shí)現(xiàn)：
public boolean isValidBST(TreeNode root) {
return isValid(root, null, null);
}
private boolean isValid(TreeNode root, Integer min, Integer max) {
if (root == null) return true;
// 當(dāng)前節(jié)點(diǎn)值必須在(min, max)范圍內(nèi)
if (min != null && root.val <= min) return false;
if (max != null && root.val >= max) return false;
// 遞歸左子樹：最大值是當(dāng)前節(jié)點(diǎn)值
// 遞歸右子樹：最小值是當(dāng)前節(jié)點(diǎn)值
return isValid(root.left, min, root.val) &&
isValid(root.right, root.val, max);
}
6.3 BST中的搜索（LeetCode 700）
遞歸實(shí)現(xiàn)：
public TreeNode searchBST(TreeNode root, int val) {
if (root == null || root.val == val) {
return root;
}
if (val < root.val) {
return searchBST(root.left, val);
} else {
return searchBST(root.right, val);
}
}
6.4 BST中的插入（LeetCode 701）
遞歸實(shí)現(xiàn)：
public TreeNode insertIntoBST(TreeNode root, int val) {
if (root == null) {
return new TreeNode(val);
}
if (val < root.val) {
root.left = insertIntoBST(root.left, val);
} else {
root.right = insertIntoBST(root.right, val);
}
return root;
}
七、二叉樹的構(gòu)建
7.1 從前序和中序構(gòu)建二叉樹（LeetCode 105）
遞歸實(shí)現(xiàn)：
public TreeNode buildTree(int[] preorder, int[] inorder) {
return build(preorder, 0, preorder.length - 1,
inorder, 0, inorder.length - 1);
}
private TreeNode build(int[] preorder, int preStart, int preEnd,
int[] inorder, int inStart, int inEnd) {
if (preStart > preEnd) return null;
// 前序遍歷的第一個(gè)元素是根節(jié)點(diǎn)
int rootVal = preorder[preStart];
TreeNode root = new TreeNode(rootVal);
// 在中序遍歷中找到根節(jié)點(diǎn)的位置
int index = inStart;
for (int i = inStart; i <= inEnd; i++) {
if (inorder[i] == rootVal) {
index = i;
break;
}
}
// 左子樹的節(jié)點(diǎn)數(shù)
int leftSize = index - inStart;
// 遞歸構(gòu)建左右子樹
root.left = build(preorder, preStart + 1, preStart + leftSize,
inorder, inStart, index - 1);
root.right = build(preorder, preStart + leftSize + 1, preEnd,
inorder, index + 1, inEnd);
return root;
}
優(yōu)化：用HashMap加速查找
// 優(yōu)化版本：用HashMap存儲(chǔ)中序遍歷的值和索引，避免每次都遍歷查找
private Map<Integer, Integer> inorderMap;
public TreeNode buildTree(int[] preorder, int[] inorder) {
// 預(yù)處理：把中序遍歷的值和索引存入HashMap
inorderMap = new HashMap<>();
for (int i = 0; i < inorder.length; i++) {
inorderMap.put(inorder[i], i);
}
return build(preorder, 0, preorder.length - 1,
inorder, 0, inorder.length - 1);
}
private TreeNode build(int[] preorder, int preStart, int preEnd,
int[] inorder, int inStart, int inEnd) {
if (preStart > preEnd) return null;
int rootVal = preorder[preStart];
TreeNode root = new TreeNode(rootVal);
// O(1)時(shí)間查找根節(jié)點(diǎn)在中序遍歷中的位置
int index = inorderMap.get(rootVal);
int leftSize = index - inStart;
root.left = build(preorder, preStart + 1, preStart + leftSize,
inorder, inStart, index - 1);
root.right = build(preorder, preStart + leftSize + 1, preEnd,
inorder, index + 1, inEnd);
return root;
}
時(shí)間復(fù)雜度： 從O(n²)優(yōu)化到O(n)
7.2 從中序和后序構(gòu)建二叉樹（LeetCode 106）
遞歸實(shí)現(xiàn)：
public TreeNode buildTree(int[] inorder, int[] postorder) {
return build(inorder, 0, inorder.length - 1,
postorder, 0, postorder.length - 1);
}
private TreeNode build(int[] inorder, int inStart, int inEnd,
int[] postorder, int postStart, int postEnd) {
if (inStart > inEnd) return null;
// 后序遍歷的最后一個(gè)元素是根節(jié)點(diǎn)
int rootVal = postorder[postEnd];
TreeNode root = new TreeNode(rootVal);
// 在中序遍歷中找到根節(jié)點(diǎn)的位置
int index = inStart;
for (int i = inStart; i <= inEnd; i++) {
if (inorder[i] == rootVal) {
index = i;
break;
}
}
int leftSize = index - inStart;
root.left = build(inorder, inStart, index - 1,
postorder, postStart, postStart + leftSize - 1);
root.right = build(inorder, index + 1, inEnd,
postorder, postStart + leftSize, postEnd - 1);
return root;
}
八、常見錯(cuò)誤和避坑指南
錯(cuò)誤1：遞歸沒有終止條件
// 錯(cuò)誤：沒有判斷root == null
public void preorder(TreeNode root) {
System.out.print(root.val + " "); // 空指針異常！
preorder(root.left);
preorder(root.right);
}
// 正確：先判斷
public void preorder(TreeNode root) {
if (root == null) return;
System.out.print(root.val + " ");
preorder(root.left);
preorder(root.right);
}
錯(cuò)誤2：混淆DFS和BFS的數(shù)據(jù)結(jié)構(gòu)
// 錯(cuò)誤：BFS用棧 Stack<TreeNode> stack = new Stack<>(); // 應(yīng)該用隊(duì)列！ // 正確：BFS用隊(duì)列 Queue<TreeNode> queue = new LinkedList<>();
錯(cuò)誤3：層序遍歷沒有記錄層數(shù)
// 錯(cuò)誤：無法區(qū)分每一層
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
// 無法知道當(dāng)前是第幾層
}
// 正確：記錄每層的節(jié)點(diǎn)數(shù)
while (!queue.isEmpty()) {
int size = queue.size(); // 當(dāng)前層的節(jié)點(diǎn)數(shù)
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
// ...
}
}
錯(cuò)誤4：判斷葉子節(jié)點(diǎn)條件錯(cuò)誤
// 錯(cuò)誤：只判斷左子節(jié)點(diǎn)
if (root.left == null) {
// 這不是葉子節(jié)點(diǎn)，可能還有右子節(jié)點(diǎn)
}
// 正確：左右子節(jié)點(diǎn)都為空
if (root.left == null && root.right == null) {
// 這才是葉子節(jié)點(diǎn)
}
錯(cuò)誤5：BST驗(yàn)證只判斷左右子節(jié)點(diǎn)
// 錯(cuò)誤：只判斷直接子節(jié)點(diǎn)
if (root.left.val < root.val && root.right.val > root.val) {
// 不夠，要判斷整個(gè)左右子樹
}
// 正確：判斷整個(gè)子樹的范圍
isValid(root.left, min, root.val);
isValid(root.right, root.val, max);
九、同類題推薦
掌握本文內(nèi)容后，可以刷這些題：
| 題號(hào) | 題目 | 難度 | 核心思路 |
|---|---|---|---|
| 144 | 二叉樹的前序遍歷 | 簡單 | DFS遞歸/迭代 |
| 94 | 二叉樹的中序遍歷 | 簡單 | DFS遞歸/迭代 |
| 145 | 二叉樹的后序遍歷 | 簡單 | DFS遞歸/迭代 |
| 102 | 二叉樹的層序遍歷 | 中等 | BFS隊(duì)列 |
| 104 | 二叉樹的最大深度 | 簡單 | 遞歸/BFS |
| 226 | 翻轉(zhuǎn)二叉樹 | 簡單 | 遞歸交換 |
| 101 | 對稱二叉樹 | 簡單 | 遞歸判斷 |
| 236 | 二叉樹的最近公共祖先 | 中等 | 遞歸查找 |
| 199 | 二叉樹的右視圖 | 中等 | BFS/DFS |
| 112 | 路徑總和 | 簡單 | 遞歸 |
| 98 | 驗(yàn)證二叉搜索樹 | 中等 | 遞歸/中序遍歷 |
| 700 | 二叉搜索樹中的搜索 | 簡單 | 遞歸/迭代 |
| 701 | 二叉搜索樹中的插入 | 中等 | 遞歸 |
| 105 | 從前序與中序構(gòu)建二叉樹 | 中等 | 遞歸構(gòu)建 |
| 106 | 從中序與后序構(gòu)建二叉樹 | 中等 | 遞歸構(gòu)建 |
十、總結(jié)
二叉樹的核心就是遞歸。 理解了遞歸，二叉樹就不難了。
兩大遍歷方式：
- DFS（深度優(yōu)先）：前序、中序、后序，用遞歸或棧
- BFS（廣度優(yōu)先）：層序遍歷，用隊(duì)列
三種DFS遍歷：
- 前序：根-左-右（先輸出根）
- 中序：左-根-右（左子樹輸出完再輸出根）
- 后序：左-右-根（左右子樹都輸出完再輸出根）
BST特性：
- 左子樹 < 根節(jié)點(diǎn) < 右子樹
- 中序遍歷是升序
學(xué)習(xí)建議：
- 先理解遞歸，畫圖模擬執(zhí)行過程
- 手寫三種DFS遍歷的遞歸代碼
- 理解BFS的隊(duì)列實(shí)現(xiàn)
- 刷簡單題鞏固（前中后序、層序、最大深度）
- 再刷中等題（翻轉(zhuǎn)、對稱、公共祖先、構(gòu)建）
到此這篇關(guān)于Java二叉樹遍歷與遞歸的文章就介紹到這了,更多相關(guān)Java二叉樹遍歷與遞歸內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
Springboot通過谷歌Kaptcha?組件生成圖形驗(yàn)證碼功能
Kaptcha是谷歌開源的一款簡單實(shí)用的圖形驗(yàn)證碼組件。我個(gè)人推薦它的最大原因是容易上手，采用約定大于配置的方式，快速契合到項(xiàng)目中，這篇文章主要介紹了Springboot通過谷歌Kaptcha組件生成圖形驗(yàn)證碼的方法,需要的朋友可以參考下2023-05-05
JSON 格式是目前最流行的數(shù)據(jù)交互格式，廣泛應(yīng)用于前后端分離的系統(tǒng)。但也有一些場合不適合使用 JSON 格式，這篇文章主要介紹了JSON 格式的弊端與解決方法,需要的朋友可以參考下2022-09-09
Shiro 是一個(gè)強(qiáng)大的簡單易用的 Java 安全框架，主要用來更便捷的 認(rèn)證，授權(quán)，加密，會(huì)話管理，這篇文章給大家詳細(xì)介紹Shiro 工作原理及架構(gòu)圖，通過實(shí)例圖文相結(jié)合給大家介紹的非常詳細(xì)，需要的朋友參考下吧2021-10-10
Bloc事件流是一個(gè)阻塞隊(duì)列結(jié)論解析
這篇文章主要為大家介紹了Bloc事件流是一個(gè)阻塞隊(duì)列結(jié)論解析，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2022-11-11
java并發(fā)編程JUC CountDownLatch線程同步
這篇文章主要介紹CountDownLatch是什么、CountDownLatch 如何工作、CountDownLatch 的代碼例子來展開對java并發(fā)編程JUC CountDownLatch線程同步，需要的朋友可以參考下面文章內(nèi)容2021-09-09
如何基于springcloud模擬RPC調(diào)用（Feign）
這篇文章主要介紹了如何基于springcloud模擬RPC調(diào)用（Feign）,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-04-04
Java實(shí)現(xiàn)AES/CBC/PKCS7Padding加解密的方法
這篇文章主要介紹了Java實(shí)現(xiàn)AES/CBC/PKCS7Padding加解密的方法，本文通過實(shí)例代碼給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2020-08-08
java計(jì)算代碼段執(zhí)行時(shí)間的詳細(xì)代碼
java里計(jì)算代碼段執(zhí)行時(shí)間可以有兩種方法，一種是毫秒級(jí)別的計(jì)算，另一種是更精確的納秒級(jí)別的計(jì)算，這篇文章主要介紹了java計(jì)算代碼段執(zhí)行時(shí)間,需要的朋友可以參考下2022-08-08
這篇文章主要介紹了spring配置掃描多個(gè)包問題解析，具有一定參考價(jià)值，需要的朋友可以了解下。2017-10-10
這篇文章主要介紹了Java 使用 FFmpeg 處理視頻文件示例代碼，代碼簡單易懂，非常不錯(cuò)，具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2020-02-02