Java 二叉树从入门到精通-遍历与递归详解

Java 二叉树从入门到精通-遍历与递归详解

二叉树不难，就是"递归+队列"

一、什么是二叉树？

1.1 生活中的二叉树

想象一个家族族谱：

 爷爷 / \ 爸爸 叔叔 / \ / \ 我 弟弟 堂哥 堂妹 

这就是一棵二叉树：

• 爷爷是根节点（最顶层）
• 爸爸和叔叔是爷爷的子节点
• 我和弟弟是爸爸的子节点
• 每个节点最多有2个子节点（左孩子、右孩子）

1.2 二叉树的定义

二叉树： 每个节点最多有两个子节点的树形结构

LeetCode标准节点结构：

/** * Definition for a binary tree node. * 这是LeetCode所有二叉树题目使用的标准结构 */publicclassTreeNode{int val;// 节点存储的值TreeNode left;// 指向左子节点的引用TreeNode right;// 指向右子节点的引用// 构造函数1：只传入值，左右子节点默认为nullTreeNode(){}// 构造函数2：传入值并初始化TreeNode(int val){this.val = val;}// 构造函数3：传入值和左右子节点TreeNode(int val,TreeNode left,TreeNode right){this.val = val;this.left = left;this.right = right;}}

举例：构建一棵树

 1 / \ 2 3 / \ 4 5 

方式1：逐个创建节点

TreeNode root =newTreeNode(1); root.left =newTreeNode(2); root.right =newTreeNode(3); root.left.left =newTreeNode(4); root.left.right =newTreeNode(5);

方式2：使用完整构造函数

TreeNode root =newTreeNode(1,newTreeNode(2,newTreeNode(4),newTreeNode(5)),newTreeNode(3));

1.3 二叉树的基本概念

节点： 树中的每个元素
根节点： 最顶层的节点（如上图的1）
叶子节点： 没有子节点的节点（如上图的3、4、5）
深度： 从根节点到当前节点的层数（根节点深度为0）
高度： 从当前节点到叶子节点的最大层数

示例：

 1 ← 根节点，深度0，高度2 / \ 2 3 ← 深度1，高度1（节点2）和0（节点3） / \ 4 5 ← 叶子节点，深度2，高度0 

1.4 特殊的二叉树

满二叉树： 每层节点都是满的，所有叶子节点在同一层

 1 / \ 2 3 / \ / \ 4 5 6 7 

特点：节点数 = 2^h - 1（h是高度）

完全二叉树： 除了最后一层，其他层都是满的，且最后一层从左到右连续

 1 / \ 2 3 / \ 4 5 

特点：适合用数组存储，堆就是完全二叉树

二叉搜索树（BST）： 左子树所有节点 < 根节点 < 右子树所有节点

 5 / \ 3 7 / \ / \ 1 4 6 9 

特点：中序遍历是升序，查找效率O(log n)

平衡二叉树（AVL树）： 任意节点的左右子树高度差不超过1

 5 / \ 3 7 / / \ 1 6 9 

特点：保证树的高度平衡，查找/插入/删除都是O(log n)

平衡二叉搜索树： 同时满足BST和平衡树的性质

 5 / \ 3 7 / \ / \ 2 4 6 8 

特点：结合了BST的有序性和平衡树的高效性，常见实现有AVL树、红黑树

对比总结：

二、二叉树的遍历方式

遍历就是"按某种顺序访问所有节点"。

2.1 两大类遍历方式

深度优先遍历（DFS）： 先往深处走，走到底再回头

• 前序遍历（根-左-右）
• 中序遍历（左-根-右）
• 后序遍历（左-右-根）

广度优先遍历（BFS）： 一层一层地访问

• 层序遍历（从上到下，从左到右）

2.2 遍历顺序对比

以这棵树为例：

 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（一层一层）

三、深度优先遍历（DFS）

3.1 前序遍历（根-左-右）

顺序： 先访问根节点，再访问左子树，最后访问右子树

递归实现（详细注释版）：

/** * 前序遍历：根-左-右 * @param root 当前节点 */publicvoidpreorder(TreeNode root){// 递归终止条件：节点为空，直接返回if(root ==null)return;// 1. 访问根节点（前序的"前"就是指这里）System.out.print(root.val +" ");// 2. 递归遍历左子树preorder(root.left);// 3. 递归遍历右子树preorder(root.right);}// 调用示例publicstaticvoidmain(String[] args){TreeNode root =newTreeNode(1,newTreeNode(2,newTreeNode(4),newTreeNode(5)),newTreeNode(3));System.out.print("前序遍历结果：");preorder(root);// 输出：1 2 4 5 3}

执行过程详解：

树： 1 / \ 2 3 / \ 4 5 执行流程（带调用栈）： 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 

迭代实现（用栈）：

publicList<Integer>preorderTraversal(TreeNode root){List<Integer> result =newArrayList<>();if(root ==null)return result;// 用栈模拟递归Stack<TreeNode> stack =newStack<>(); stack.push(root);while(!stack.isEmpty()){// 弹出栈顶节点并访问TreeNode node = stack.pop(); result.add(node.val);// 先压右子树，再压左子树（栈是后进先出，所以先压右边）if(node.right !=null) stack.push(node.right);if(node.left !=null) stack.push(node.left);}return result;}

3.2 中序遍历（左-根-右）

顺序： 先访问左子树，再访问根节点，最后访问右子树

递归实现（详细注释版）：

/** * 中序遍历：左-根-右 * @param root 当前节点 */publicvoidinorder(TreeNode root){// 递归终止条件if(root ==null)return;// 1. 先递归遍历左子树inorder(root.left);// 2. 访问根节点（中序的"中"就是指这里，在中间访问）System.out.print(root.val +" ");// 3. 最后递归遍历右子树inorder(root.right);}// 调用示例publicstaticvoidmain(String[] args){TreeNode root =newTreeNode(1,newTreeNode(2,newTreeNode(4),newTreeNode(5)),newTreeNode(3));System.out.print("中序遍历结果：");inorder(root);// 输出：4 2 5 1 3}

执行过程详解：

树： 1 / \ 2 3 / \ 4 5 执行流程（带调用栈）： 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 

迭代实现（用栈）：

publicList<Integer>inorderTraversal(TreeNode root){List<Integer> result =newArrayList<>();Stack<TreeNode> stack =newStack<>();TreeNode curr = root;while(curr !=null||!stack.isEmpty()){// 一直往左走，把所有左节点压栈while(curr !=null){ stack.push(curr); curr = curr.left;}// 弹出栈顶节点，访问 curr = stack.pop(); result.add(curr.val);// 转向右子树 curr = curr.right;}return result;}

3.3 后序遍历（左-右-根）

顺序： 先访问左子树，再访问右子树，最后访问根节点

递归实现（详细注释版）：

/** * 后序遍历：左-右-根 * @param root 当前节点 */publicvoidpostorder(TreeNode root){// 递归终止条件if(root ==null)return;// 1. 先递归遍历左子树postorder(root.left);// 2. 再递归遍历右子树postorder(root.right);// 3. 最后访问根节点（后序的"后"就是指这里，最后访问）System.out.print(root.val +" ");}// 调用示例publicstaticvoidmain(String[] args){TreeNode root =newTreeNode(1,newTreeNode(2,newTreeNode(4),newTreeNode(5)),newTreeNode(3));System.out.print("后序遍历结果：");postorder(root);// 输出：4 5 2 3 1}

执行过程详解：

树： 1 / \ 2 3 / \ 4 5 执行流程（带调用栈）： 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 

迭代实现（用栈）：

publicList<Integer>postorderTraversal(TreeNode root){List<Integer> result =newArrayList<>();if(root ==null)return result;Stack<TreeNode> stack =newStack<>(); stack.push(root);while(!stack.isEmpty()){TreeNode node = stack.pop(); result.add(0, node.val);// 插入到结果开头// 先压左子树，再压右子树if(node.left !=null) stack.push(node.left);if(node.right !=null) stack.push(node.right);}return result;}

3.4 三种遍历的对比

记忆技巧：

• 前序：根节点在前面（先输出根）
• 中序：根节点在中间（左子树输出完再输出根）
• 后序：根节点在后面（左右子树都输出完再输出根）

四、广度优先遍历（BFS）

4.1 层序遍历

顺序： 从上到下，从左到右，一层一层访问

示例：

 1 / \ 2 3 / \ 4 5 层序遍历：1 → 2 → 3 → 4 → 5 

实现（用队列）：

publicList<Integer>levelOrder(TreeNode root){List<Integer> result =newArrayList<>();if(root ==null)return result;// 用队列实现层序遍历Queue<TreeNode> queue =newLinkedList<>(); queue.offer(root);while(!queue.isEmpty()){// 弹出队首节点并访问TreeNode node = queue.poll(); result.add(node.val);// 先加左子节点，再加右子节点（队列是先进先出）if(node.left !=null) queue.offer(node.left);if(node.right !=null) queue.offer(node.right);}return result;}

执行过程：

初始：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 = [] 结果：1 2 3 4 5 

4.2 分层输出（重要）

需求： 输出每一层的节点

示例：

 1 / \ 2 3 / \ 4 5 输出： [[1], [2,3], [4,5]] 

实现：

publicList<List<Integer>>levelOrder(TreeNode root){List<List<Integer>> result =newArrayList<>();if(root ==null)return result;Queue<TreeNode> queue =newLinkedList<>(); queue.offer(root);while(!queue.isEmpty()){int size = queue.size();// 当前层的节点数（关键！）List<Integer> level =newArrayList<>();// 遍历当前层的所有节点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;}

关键：int size = queue.size() 记录当前层的节点数

4.3 DFS vs BFS

记忆技巧：

• DFS = 深（Deep）= 栈（Stack）= 递归
• BFS = 宽（Broad）= 队列（Queue）= 层序

五、二叉树的经典问题

5.1 求二叉树的最大深度（LeetCode 104）

题目： 给定一个二叉树，找出其最大深度。

示例：

 3 / \ 9 20 / \ 15 7 最大深度：3 

思路： 树的深度 = max(左子树深度, 右子树深度) + 1

递归实现：

publicintmaxDepth(TreeNode root){// 空节点深度为0if(root ==null)return0;// 递归计算左右子树深度int leftDepth =maxDepth(root.left);int rightDepth =maxDepth(root.right);// 当前节点深度 = 左右子树最大深度 + 1returnMath.max(leftDepth, rightDepth)+1;}

5.2 翻转二叉树（LeetCode 226）

题目： 翻转一棵二叉树。

递归实现：

publicTreeNodeinvertTree(TreeNode root){if(root ==null)returnnull;// 交换左右子树TreeNode temp = root.left; root.left = root.right; root.right = temp;// 递归翻转左右子树invertTree(root.left);invertTree(root.right);return root;}

5.3 对称二叉树（LeetCode 101）

题目： 判断一棵二叉树是否对称。

递归实现：

publicbooleanisSymmetric(TreeNode root){if(root ==null)returntrue;returnisMirror(root.left, root.right);}privatebooleanisMirror(TreeNode left,TreeNode right){if(left ==null&& right ==null)returntrue;if(left ==null|| right ==null)returnfalse;if(left.val != right.val)returnfalse;returnisMirror(left.left, right.right)&&isMirror(left.right, right.left);}

5.4 二叉树的最近公共祖先（LeetCode 236）

递归实现：

publicTreeNodelowestCommonAncestor(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实现：

publicList<Integer>rightSideView(TreeNode root){List<Integer> result =newArrayList<>();if(root ==null)return result;Queue<TreeNode> queue =newLinkedList<>(); queue.offer(root);while(!queue.isEmpty()){int size = queue.size();for(int i =0; i < size; i++){TreeNode node = queue.poll();// 每层的最后一个节点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）

递归实现：

publicbooleanhasPathSum(TreeNode root,int targetSum){if(root ==null)returnfalse;// 叶子节点，判断是否等于目标和if(root.left ==null&& root.right ==null){return root.val == targetSum;}// 递归左右子树，目标和减去当前节点值returnhasPathSum(root.left, targetSum - root.val)||hasPathSum(root.right, targetSum - root.val);}

六、二叉搜索树（BST）

6.1 什么是二叉搜索树？

定义： 左子树所有节点 < 根节点 < 右子树所有节点

示例：

 5 / \ 3 7 / \ / \ 1 4 6 9 

特点： 中序遍历BST，得到的是升序序列

中序遍历： 1 → 3 → 4 → 5 → 6 → 7 → 9（升序）

6.2 验证二叉搜索树（LeetCode 98）

递归实现：

publicbooleanisValidBST(TreeNode root){returnisValid(root,null,null);}privatebooleanisValid(TreeNode root,Integer min,Integer max){if(root ==null)returntrue;// 当前节点值必须在(min, max)范围内if(min !=null&& root.val <= min)returnfalse;if(max !=null&& root.val >= max)returnfalse;// 递归左子树：最大值是当前节点值// 递归右子树：最小值是当前节点值returnisValid(root.left, min, root.val)&&isValid(root.right, root.val, max);}

6.3 BST中的搜索（LeetCode 700）

递归实现：

publicTreeNodesearchBST(TreeNode root,int val){if(root ==null|| root.val == val){return root;}if(val < root.val){returnsearchBST(root.left, val);}else{returnsearchBST(root.right, val);}}

6.4 BST中的插入（LeetCode 701）

递归实现：

publicTreeNodeinsertIntoBST(TreeNode root,int val){if(root ==null){returnnewTreeNode(val);}if(val < root.val){ root.left =insertIntoBST(root.left, val);}else{ root.right =insertIntoBST(root.right, val);}return root;}

七、二叉树的构建

7.1 从前序和中序构建二叉树（LeetCode 105）

递归实现：

publicTreeNodebuildTree(int[] preorder,int[] inorder){returnbuild(preorder,0, preorder.length -1, inorder,0, inorder.length -1);}privateTreeNodebuild(int[] preorder,int preStart,int preEnd,int[] inorder,int inStart,int inEnd){if(preStart > preEnd)returnnull;// 前序遍历的第一个元素是根节点int rootVal = preorder[preStart];TreeNode root =newTreeNode(rootVal);// 在中序遍历中找到根节点的位置int index = inStart;for(int i = inStart; i <= inEnd; i++){if(inorder[i]== rootVal){ index = i;break;}}// 左子树的节点数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;}

优化：用HashMap加速查找

// 优化版本：用HashMap存储中序遍历的值和索引，避免每次都遍历查找privateMap<Integer,Integer> inorderMap;publicTreeNodebuildTree(int[] preorder,int[] inorder){// 预处理：把中序遍历的值和索引存入HashMap inorderMap =newHashMap<>();for(int i =0; i < inorder.length; i++){ inorderMap.put(inorder[i], i);}returnbuild(preorder,0, preorder.length -1, inorder,0, inorder.length -1);}privateTreeNodebuild(int[] preorder,int preStart,int preEnd,int[] inorder,int inStart,int inEnd){if(preStart > preEnd)returnnull;int rootVal = preorder[preStart];TreeNode root =newTreeNode(rootVal);// O(1)时间查找根节点在中序遍历中的位置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;}

时间复杂度： 从O(n²)优化到O(n)

7.2 从中序和后序构建二叉树（LeetCode 106）

递归实现：

publicTreeNodebuildTree(int[] inorder,int[] postorder){returnbuild(inorder,0, inorder.length -1, postorder,0, postorder.length -1);}privateTreeNodebuild(int[] inorder,int inStart,int inEnd,int[] postorder,int postStart,int postEnd){if(inStart > inEnd)returnnull;// 后序遍历的最后一个元素是根节点int rootVal = postorder[postEnd];TreeNode root =newTreeNode(rootVal);// 在中序遍历中找到根节点的位置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;}

八、常见错误和避坑指南

错误1：递归没有终止条件

// 错误：没有判断root == nullpublicvoidpreorder(TreeNode root){System.out.print(root.val +" ");// 空指针异常！preorder(root.left);preorder(root.right);}// 正确：先判断publicvoidpreorder(TreeNode root){if(root ==null)return;System.out.print(root.val +" ");preorder(root.left);preorder(root.right);}

错误2：混淆DFS和BFS的数据结构

// 错误：BFS用栈Stack<TreeNode> stack =newStack<>();// 应该用队列！// 正确：BFS用队列Queue<TreeNode> queue =newLinkedList<>();

错误3：层序遍历没有记录层数

// 错误：无法区分每一层while(!queue.isEmpty()){TreeNode node = queue.poll();// 无法知道当前是第几层}// 正确：记录每层的节点数while(!queue.isEmpty()){int size = queue.size();// 当前层的节点数for(int i =0; i < size; i++){TreeNode node = queue.poll();// ...}}

错误4：判断叶子节点条件错误

// 错误：只判断左子节点if(root.left ==null){// 这不是叶子节点，可能还有右子节点}// 正确：左右子节点都为空if(root.left ==null&& root.right ==null){// 这才是叶子节点}

错误5：BST验证只判断左右子节点

// 错误：只判断直接子节点if(root.left.val < root.val && root.right.val > root.val){// 不够，要判断整个左右子树}// 正确：判断整个子树的范围isValid(root.left, min, root.val);isValid(root.right, root.val, max);

九、同类题推荐

掌握本文内容后，可以刷这些题：

十、总结

二叉树的核心就是递归。 理解了递归，二叉树就不难了。

两大遍历方式：

• DFS（深度优先）：前序、中序、后序，用递归或栈
• BFS（广度优先）：层序遍历，用队列

三种DFS遍历：

• 前序：根-左-右（先输出根）
• 中序：左-根-右（左子树输出完再输出根）
• 后序：左-右-根（左右子树都输出完再输出根）

BST特性：

• 左子树 < 根节点 < 右子树
• 中序遍历是升序

学习建议：

1. 先理解递归，画图模拟执行过程
2. 手写三种DFS遍历的递归代码
3. 理解BFS的队列实现
4. 刷简单题巩固（前中后序、层序、最大深度）
5. 再刷中等题（翻转、对称、公共祖先、构建）

作者：[识君啊]

不要做API的搬运工，要做原理的探索者！