Java开发者必会：手写二叉树遍历与递归实战-北京尧图网络

1. 为什么我建议每个Java开发者都认真手写一遍二叉树二叉树这个数据结构在Java开发里出现的频率远比你想象中要高。工作三年以上的服务端开发者多多少少都会在代码评审里见过红黑树相关的TreeMap、TreeSet源码或者在生产环境排查过HashMap在极端情况下的树化问题。但真正能脱稿写出二叉树遍历、翻转、求深度这些基础操作的人比例其实不高。原因很简单平时业务代码写得多树的逻辑被各种框架封装掉了用不到就生疏了。但面试几乎是必考的。更重要的是二叉树的思维方式——递归、分治、层级的抽象——会在你写业务逻辑时潜移默化地起作用。我见过不少同事在处理组织结构树、评论区的多级回复、权限菜单的层级展示时思路混乱代码写得又长又绕。如果能把二叉树的基本功打牢这类业务场景的代码会清晰得多。这篇文章不聊虚的。我用自己的实战经验把二叉树的Java实现从头到尾拆一遍包括节点定义、递归与非递归遍历、常见操作求深度、判断平衡、翻转树等以及刷题和实际开发中踩过的一些坑。适合三类人看正在准备面试的Java开发者、工作中需要处理树形数据的后端开发、以及想系统梳理数据结构基础的在校学生。2. 二叉树的核心设计思路从现实模型到代码抽象2.1 二叉树的定义与Java表达先明确一点二叉树到底是什么。用人话说二叉树是一种每个节点最多只有两个子节点的树形结构左边的叫左孩子右边的叫右孩子。这两个孩子有严格的左右顺序调换位置就变成了另一棵树。在Java里表达一个二叉树节点最朴素的方式就是写一个内部类public 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; } }就这么简单。一个字段存值两个字段分别指向左子树和右子树的根节点。空指针表示“这里没有子树了”。理解了这个结构就能理解二叉树后续所有操作的递归本质——因为树本身就是递归定义的一棵二叉树要么为空要么由一个根节点和左右两棵二叉树组成。这里我得强调一个很多新手容易忽略的点二叉树不是链表但它的存储结构和双向链表有着相似之处。链表是线性结构只有前后关系二叉树是层级结构有父子、兄弟关系和深度概念。但两者在Java里都是用引用指针串联起来的所以在写代码时要时刻注意空指针的边界。2.2 为什么二叉树问题几乎都是递归问题二叉树本身就是递归定义的所以你用递归去处理它是天然契合的。每次递归本质上是在做同一件事处理当前节点然后交给左右子树。我用一个生活类比来解释。想象你在组织一场公司年会你是最大的领导你需要通知你的两个副手他们再分别通知自己的下属。这个通知的过程就是递归每个人只需要通知自己的直接下属一层层往下传直到没有下属为止。二叉树的递归遍历就是这个感觉只是这里的“下属”固定只有两个——左和右。递归代码的好处是简洁、直观、符合人类思维。坏处是如果递归深度太大JVM的调用栈会溢出。这个问题我在讲遍历的时候会专门展开。2.3 二叉树的分类不只是“一棵树”那么简单在Java里做二叉树你得先分清自己在处理哪种树因为不同的树有不同的性质处理方式也不同。满二叉树每一层节点都满了最后一层全是叶子。这种树形状完美总节点数等于 2^深度 - 1。完全二叉树除了最后一层其他层都满了最后一层的节点从左到右连续排列。堆PriorityQueue的底层结构就是完全二叉树。二叉搜索树BST左子树所有节点的值都小于根节点右子树所有节点的值都大于根节点左右子树各自也满足这个性质。这个树有个好处——中序遍历的结果就是有序的。平衡二叉树AVL树 / 红黑树在BST基础上增加了平衡约束防止树退化成链表。Java的TreeMap就是红黑树实现的。不同的树操作时的判断逻辑完全不同。比如搜索普通二叉树只能遍历二叉搜索树可以按值减半查找。我在实际中见过同事把普通二叉树当搜索树用遍历半天找不到目标值最后发现是因为树本身没有排序约束——这是概念没分清导致的低级BUG。3. 用Java手写二叉树的核心实操构建、遍历与经典操作3.1 如何手动构建一棵二叉树在实际开发中二叉树最常见的数据来源有两种。一种是线性数据结构转换来的比如数组、列表另一种是递归构建的比如根据业务数据生成组织结构树。先说手动构建这种场景在做算法题、写单元测试时最常用。比如我要构建这样一棵树1 / \ 2 3 / \ \ 4 5 6用Java代码构建就是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); root.right.right new TreeNode(6);就这么直接一个个把节点new出来然后把孩子挂上去。这是调试和测试时最可靠的方式我建议每个初学者都至少手动建过三棵以上结构不同的树。因为只有亲手把每个节点的引用关系理顺了才能真正理解“节点是节点结构是结构”这件事——节点之间是通过引用建立结构的节点本身并不知道自己是谁的左孩子还是右孩子。再说说从数组构建二叉树的场景。很多人一开始会误以为数组转二叉树是那样一股脑塞进去就行其实不然。数组只是我们通过某个线性序列去描述树形结构最常用的是层序序列化方式即每一层从左到右放。构建的核心是利用队列一层层把节点挂上去。public static TreeNode createTree(Integer[] arr) { if (arr null || arr.length 0) { return null; } TreeNode root new TreeNode(arr[0]); QueueTreeNode queue new LinkedList(); queue.offer(root); int index 1; while (!queue.isEmpty() index arr.length) { TreeNode node queue.poll(); if (arr[index] ! null) { node.left new TreeNode(arr[index]); queue.offer(node.left); } index; if (index arr.length arr[index] ! null) { node.right new TreeNode(arr[index]); queue.offer(node.right); } index; } return root; }注意这里的细节用Integer而不是int因为需要用null表示“没有这个子节点”。我们用队列保存所有待挂接孩子的节点每弹出一个就尝试给它挂左右孩子。这个build过程本身就是一个层序遍历的逆用理解了它你也就理解了层序遍历的核心思想。3.2 二叉树的遍历递归与非递归的完整实现遍历是二叉树最基础也最重要的操作就像出门前要会系鞋带一样。遍历分四种前序、中序、后序、层序。前三种是深度优先遍历DFS最后一种是广度优先遍历BFS。前序遍历根节点 → 左子树 → 右子树。就是优先处理当前节点再去管孩子。递归写法非常简短public void preorder(TreeNode root) { if (root null) { return; } System.out.print(root.val ); preorder(root.left); preorder(root.right); }中序遍历左子树 → 根节点 → 右子树。这个顺序在二叉搜索树里非常关键因为中序遍历BST得到的是升序序列。public void inorder(TreeNode root) { if (root null) { return; } inorder(root.left); System.out.print(root.val ); inorder(root.right); }后序遍历左子树 → 右子树 → 根节点。这个顺序在做“自底向上”的计算时特别有用比如求二叉树的最大深度、释放资源等场景。public void postorder(TreeNode root) { if (root null) { return; } postorder(root.left); postorder(root.right); System.out.print(root.val ); }三个递归版本长得几乎一样只是打印语句的位置不同。这个“位置不同”正是三种遍历的核心区别。理解了这三个位置递归遍历就掌握了八成了。但递归写法有个致命弱点——树的高度如果很大比如几万层递归会栈溢出。这时候就需要迭代写法。迭代写法需要手动使用栈来模拟递归调用过程。我用前序遍历举例。前序的顺序是根-左-右我们可以先把根入栈然后循环弹栈处理节点处理完先把右孩子入栈再入左孩子。因为栈是先进后出先入右再入左弹出的顺序就是左先右后正好满足前序要求。public void preorderIteration(TreeNode root) { if (root null) { return; } DequeTreeNode stack new ArrayDeque(); stack.push(root); while (!stack.isEmpty()) { TreeNode node stack.pop(); System.out.print(node.val ); if (node.right ! null) { stack.push(node.right); } if (node.left ! null) { stack.push(node.left); } } }中序和前序的迭代写法差异较大因为中序要求先处理左子树再回到根。这里有一个关键的思路不能把节点弹出来就处理得一路往左走到底把沿途经过的节点全部入栈直到走到空才弹出栈顶处理然后转向右孩子。public void inorderIteration(TreeNode root) { if (root null) { return; } DequeTreeNode stack new ArrayDeque(); TreeNode cur root; while (cur ! null || !stack.isEmpty()) { while (cur ! null) { stack.push(cur); cur cur.left; } cur stack.pop(); System.out.print(cur.val ); cur cur.right; } }后序的迭代相对更绕但有一个取巧的办法用两栈法或者用一个栈加一个标记。我更推荐一个“偷懒但实用”的技巧——因为后序是左-右-根前序是根-左-右如果我们把前序改成“根-右-左”然后整体反转输出结果就是后序。这个思路在代码里就是加一个辅助栈收集结果再倒序。层序遍历BFS用的不是栈而是队列从根开始一层一层地遍历。每一层从左到右处理。public void levelOrder(TreeNode root) { if (root null) { return; } QueueTreeNode queue new LinkedList(); queue.offer(root); while (!queue.isEmpty()) { TreeNode node queue.poll(); System.out.print(node.val ); if (node.left ! null) { queue.offer(node.left); } if (node.right ! null) { queue.offer(node.right); } } }这里有个面试高频变体要求按“每一层一行”输出比如把第1层放在一个List里第2层放在另一个List里。实现方式就是在while循环里先把当前queue的size记录下来然后连续处理size个节点这样就能天然切分出一层。public ListListInteger levelOrderByLevel(TreeNode root) { ListListInteger result new ArrayList(); if (root null) { return result; } QueueTreeNode queue new LinkedList(); queue.offer(root); while (!queue.isEmpty()) { int size queue.size(); ListInteger level new ArrayList(); 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; }这个“按层切分”的技巧我强烈建议背下来因为它几乎是层序遍历类题目的万能模板。3.3 经典操作实战求深度、翻转树、判断平衡遍历只是基础真正应用二叉树的地方在于对树结构进行运算和改造。下面这几个操作是我在面试和实际业务场景中高频碰到的。求二叉树的最大深度。深度就是根节点到最远叶子节点的节点数也可以理解成树的层数。递归写法只有三行public int maxDepth(TreeNode root) { if (root null) { return 0; } return 1 Math.max(maxDepth(root.left), maxDepth(root.right)); }这个代码的逻辑非常优雅一棵树的最大深度左子树深度和右子树深度的较大值加上根节点这一层。典型的后序遍历思路——先算子树再算当前层。理解这个式子之后你会发现“自底向上的递归”这个说法不再是抽象的它就是这样一个不断把子问题的答案往上抛的过程。迭代写法也顺手给出来用层序遍历每走完一层深度加1public int maxDepthIteration(TreeNode root) { if (root null) { return 0; } QueueTreeNode queue new LinkedList(); queue.offer(root); int depth 0; while (!queue.isEmpty()) { int size queue.size(); for (int i 0; i size; i) { TreeNode node queue.poll(); if (node.left ! null) { queue.offer(node.left); } if (node.right ! null) { queue.offer(node.right); } } depth; } return depth; }翻转二叉树。就是把每个节点的左右子树交换。这题在面试里出镜率很高但实际业务中也有应用场景比如前端做右侧拉菜单时想镜像展示树形结构。递归写法极其对称public TreeNode invertTree(TreeNode root) { if (root null) { return null; } TreeNode left invertTree(root.left); TreeNode right invertTree(root.right); root.left right; root.right left; return root; }你可以对照前序、后序遍历理解。这里的处理顺序是先递归左右子树相当于后序然后交换。也可以先交换再递归相当于前序都能得到正确结果。关键在于每个节点都只交换它的两个孩子然后让它的孩子递归地去交换各自的孩子的孩子简单说就是“你只管自己这一层剩下的交给下层”。判断一棵树是否平衡。平衡的定义任意节点的左右子树高度差不超过1。这里不能简单定义“根节点的左右子树高度差不超过1”因为某个很深的子树下方可能不平衡。所以正确的做法是递归判断每个节点。我用一个带剪枝的思路计算深度的同时判断是否平衡public boolean isBalanced(TreeNode root) { return height(root) ! -1; } private int height(TreeNode node) { if (node null) { return 0; } int left height(node.left); if (left -1) { return -1; } int right height(node.right); if (right -1) { return -1; } if (Math.abs(left - right) 1) { return -1; } return 1 Math.max(left, right); }这里用返回-1作为“已经不平衡”的特殊标记。这个写法的精妙之处在于它把“求高度”和“判断平衡”合并成了一个函数一旦发现不平衡就提前返回避免了多余的递归计算。我在面试时很喜欢看候选人能不能想到这种带剪枝的做法因为这说明他对递归的理解不是刻板的。3.4 交叉验证基础操作之间的依赖关系以上几类操作并不是孤立的而是一个体系。搜索和删除这类操作需要依赖遍历去定位节点而定位的效率和树的有序性直接挂钩。比如在BST里删除节点需要先通过搜索找到目标节点然后分三种情况处理叶子节点直接删、只有一个孩子的节点让其孩子顶替、有两个孩子的节点找中序后继或前驱来替换。public TreeNode deleteNode(TreeNode root, int key) { if (root null) { return null; } if (key root.val) { root.left deleteNode(root.left, key); } else if (key root.val) { root.right deleteNode(root.right, key); } else { // 找到了目标节点 if (root.left null) { return root.right; } if (root.right null) { return root.left; } // 有两个孩子找右子树中的最小值中序后继 TreeNode minNode root.right; while (minNode.left ! null) { minNode minNode.left; } root.val minNode.val; root.right deleteNode(root.right, root.val); } return root; }我建议学习二叉树时按这个顺序进阶先手动构建树再写通递归遍历再写迭代遍历然后做深度、翻转、判断平衡这类操作最后涉足二叉搜索树的插入删除。每一步都建立在前一步的基础上跳着学容易卡壳。4. 二叉树Java实现中的常见问题与排查技巧实录4.1 空指针异常的根源引用悬挂与结构破坏二叉树操作中最常见的运行时异常就是NullPointerException。主要分两类。第一类是遍历或访问时没有判空。比如在递归遍历中直接写root.left.val而不确保root.left不为空一旦左孩子是null就炸了。解决方法是让根节点为空的判断成为递归函数的第一行这叫“递归出口”它决定了整个递归函数的安全边界。我在审查代码时如果看到一个递归方法的第一行不是判空会立刻打上疑问标记。第二类是构建树时引用悬挂。比如你把节点A的左孩子设置为B后来又创建了一个C并设置A的左孩子为C那么原来的B就“丢了”——没有任何引用指向它Java的GC会回收它但你的本意可能是把B和C同时挂在A下面这在二叉树里是做不到的。完整二叉树的定义就注定了每个节点只能有一个父节点。实际工作中有人想用二叉树存多叉结构比如组织架构结果发现丢节点就是这个原因。4.2 递归溢出的症状识别与迭代改写递归深度过大时JVM会抛出StackOverflowError。这在二叉树退化成链表时特别常见。比如一棵二叉搜索树如果按升序插入数据它的形状就是一条直线深度等于节点数。这时候做递归中序几千个节点就可能把栈打爆。我实际测过JVM默认栈深度大概在一万层左右不同环境和JVM参数差异很大不要依赖这个数字安全做法是当预估树的深度超过几千层时直接用迭代写法。面试时如果考题明确说明节点数在10^5量级那你应该条件反射地放弃递归改用栈或队列的迭代实现。还有一个容易踩的坑是递归方法里创建大量局部对象这会加速栈溢出。尽量少在递归里new对象能用基本类型就用基本类型。4.3 剪枝失败与错误的结构假设有些问题你以为自己写的递归是对的但结果就是不对。常见原因有返回类型设计不对。比如判断平衡时返回boolean但递归过程又需要子树高度于是你又写了一个求高度的函数两套递归相互调用既慢又容易出错。改用返回-1表示不平衡的写法能同时解决两个问题。终止条件缺失或不完整。比如计算“路径总和”这类问题时你要明确“叶子节点”的定义是左右孩子都为空而不是“当前节点为空”。把空节点当成叶子会多算或少算路径。误把二叉搜索树的特性套在普通二叉树上。比如在普通二叉树里做查找却按BST的大小判断逻辑去剪枝直接把节点搜丢了。一定要先分辨清楚你操作的是什么性质的树。我这里给出一份快速排查清单平时调试二叉树算法时按这个顺序自查递归出口的判空是否在最前面判空条件覆盖了哪些情况递归处理的结果是否正确传递给了上层调用对当前节点的处理顺序是否符合该题要求的遍历顺序是否混淆了“节点值相等”和“节点引用相同”是否考虑了树的形状特征比如是否是BST、是否平衡数据结构用对了吗DFS用栈BFS用队列4.4 二叉树的序列化与调试技巧调试二叉树最痛苦的是看不到结构。不像数组可以一行打印出来树形结构打印出来很难看。我建议在本地维护一段工具代码把二叉树按层序遍历输出成数组形式方便对比。一个能看的调试方法是用“括号表示法”打印树形如1(2(4,5),3(,6))。这种格式能清楚地表达节点的父子关系比自己脑补强得多。实现起来也不难递归拼接字符串即可。另一个我在实际用过很多次的技巧用层序序列化的数组中间态来验算。你先把一棵树的层序数组写出来然后用createTree方法构建一棵树再把树层序遍历打印出来对比一下是否一致。一致说明你的构建和遍历代码都没问题之后在这个基础上做其他操作出问题时就能确定不是底层代码的锅。还有个容易被忽视的细节Java的ArrayDeque比Stack更好用。Stack是遗留类继承自Vector有同步开销性能不如ArrayDeque。Deque提供了push、pop、peek等方法语义上完全够用。我建议写迭代遍历统一用ArrayDeque不要用Stack。5. 面试与实战中的二叉树经验补充5.1 三类高频二叉树题型的识别与应对我在面试辅导和多轮技术招聘中发现二叉树的题目其实就三大类套路非常明显。第一类遍历类。让你按某种顺序输出节点不管是前中后序还是层序核心就是背熟递归和迭代两种模板。有的题目会变着花样考比如Z字形层序遍历其实就在层序模板上对偶数层做一次反转。比如求右视图就把每层的最后一个节点加入结果。认清了它们的本质再花哨的变形都能拆回基础模板。第二类自顶向下类。典型如“判断两棵树是否相同”“判断一棵树是否是另一棵的子树”“路径总和”等。这类题的核心是在递归过程中维护当前路径或比较状态把上层的结果传给下层。比如判断路径总和是否存在就是累加当前节点值到叶子时判断是否等于目标值。第三类自底向上类。典型如“求最大深度”“求最近公共祖先”“判断平衡二叉树”。思路是先处理好左右子树再把子问题结果汇总到当前节点。写这类题时递归函数要返回“子树计算后的结果”当前节点负责合并左右结果。我把这三类题的思路对比一下题型核心思路代表题目典型写法遍历类按顺序访问节点前中后序、层序递归/栈/队列模板自顶向下把状态从根往下传路径总和、子树判断递归时携带参数自底向上从叶子往上汇总最大深度、公共祖先先递归后处理这个分类法能帮你快速定位题目类型然后匹配做题模板效率会高很多。5.2 二叉树和其它数据结构的关系二叉树不是孤立的它和其它数据结构有千丝万缕的联系。理解这些联系你才能真正融会贯通。与数组的关系完全二叉树可以用数组存储父节点下标为i时左孩子下标为2i1右孩子为2i2从0开始。堆排序就是利用了这种关系。与链表的关系二叉树节点的存储结构本质上是引用连接只是从一维的链变成了二维的分叉。很多链表操作技巧比如快慢指针在树上有了新的变体比如找树中位数。与图的关联二叉树是图的特例是没有环的连通性结构。很多图的BFS/DFS思路起源于树的遍历。与业务表结构的关联数据库的索引尤其是MySQL的InnoDB存储引擎底层用的就是B树而B树的思想源头就是二叉搜索树的变种。理解了二叉树的搜索逻辑再去看数据库索引原理会顺畅很多。我在转Java服务端开发第二年的那个阶段需要设计一个评论系统的多级回复数据量不大但层级深用递归从数据库查出来组装成一棵评论树。当时我二叉树知识还很浅写出来的递归代码又慢又容易乱后来把树的遍历思路彻底理顺了代码重写了一遍效率提升明显。这不是在夸耀而是想说树形结构在业务中的出场频率真的很高值得你花时间系统掌握。5.3 从二叉树到进阶数据结构的延伸路线把基础二叉树搞透之后想再进一步的话我给的路径是二叉搜索树BST在二叉树基础上增加有序性学会插入、删除、搜索理解中序遍历有序的性质。平衡二叉搜索树AVL树掌握LL、RR、LR、RL四种旋转操作理解什么情况下树会失衡以及如何恢复平衡。红黑树理解它的5条性质了解为什么Java的TreeMap和HashMap树化后选择红黑树而不是AVL树根本原因在于红黑树的插入删除旋转次数更少性能更稳定。B树与B树跳出二叉树理解多路搜索树看数据库索引和文件系统如何利用宽而浅的树结构减少磁盘IO。Trie树前缀树处理字符串搜索、敏感词过滤等场景核心思路是把公共前缀合并存储。这条路线走下来你已经超越了大多数同级别的Java开发者。不夸张地说如果你能在不看参考代码的情况下独立写出AVL树的插入和旋转你应对绝大多数公司的数据结构面试都绰绰有余了。我个人在实际调二叉树代码的过程里有一个深刻的体会很多bug不是逻辑想错了而是对递归的基本单位没有想清楚。你写递归之前先问自己三个问题这个函数的作用是什么递归出口在哪返回值向上层传递的是什么想清楚了再动手写出来的代码基本一次通过。这三个问题同样适用于工作和面试中遇到的所有递归类问题。

Java开发者必会：手写二叉树遍历与递归实战

相关推荐

Java二叉树实战：从递归遍历到迭代实现与经典应用

告别熬夜排版：建立稳定排版SOP，半小时高效出稿

Android隐私保护利器Amarok-Hider：一键隐藏文件与应用实战指南

更多资讯

嵌入式驱动开发：量产级工程化实战第 21 篇：配置管理与远程升级

如何快速获取 gemma-2-2b_rai_1.8.0_medusa_1.0_npu：ModelScope SDK + Git Clone 双方式下载教程

instagram-private-api 评论响应接口 MediaRepositoryCommentResponse 深度解析：结构、字段与实战调用

Octopus 实空间 TDDFT 模拟：从光吸收谱到电子动力学实战指南

导弹打飞机贪心算法：最少拦截系统与偏序链覆盖详解

OpenCore Legacy Patcher 指南：老 Mac 装新 macOS 的完整流程

今日更新

Cephadm实战指南：Linux系统工程师的生产级Ceph集群部署与排障

不想再被 Token 额度卡脖子？把免费 API 接入 WorkBuddy 的完整教程

ITK中SpatialObject几何体系解析：坐标系、变换与管道集成

本周精选

交通拥堵预测毕设：基于Python+LSTM的车辆流量预测系统全流程解析

MATLAB/Simulink搭建10机39节点电力系统暂态稳定仿真实战

无人机航拍三维重建全流程：从SfM到网格生成的避坑指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？