Java实现二叉树遍历与常见算法解析

1. 项目概述最近在力扣(LeetCode)上集中练习了几道经典的二叉树题目包括二叉树的中序遍历、对称二叉树、二叉树的最大深度以及买卖股票的最佳时机。这些题目看似基础但实际编码时会遇到各种边界条件和实现细节的挑战。作为Java开发者我记录下这些题目的解题思路和代码实现特别是一些容易踩坑的地方。2. 二叉树中序遍历实现2.1 递归解法二叉树的中序遍历顺序是左子树 - 根节点 - 右子树。递归实现是最直观的方式public ListInteger inorderTraversal(TreeNode root) { ListInteger res new ArrayList(); inorder(root, res); return res; } private void inorder(TreeNode node, ListInteger res) { if (node null) return; inorder(node.left, res); res.add(node.val); inorder(node.right, res); }注意递归解法虽然简洁但当树很深时可能导致栈溢出。对于极端不平衡的树(如链表状的树)递归深度可能达到O(n)。2.2 迭代解法使用栈模拟递归过程public ListInteger inorderTraversal(TreeNode root) { ListInteger res new ArrayList(); StackTreeNode stack new Stack(); TreeNode curr root; while (curr ! null || !stack.isEmpty()) { while (curr ! null) { stack.push(curr); curr curr.left; } curr stack.pop(); res.add(curr.val); curr curr.right; } return res; }这个解法的时间复杂度是O(n)空间复杂度最坏情况下也是O(n)。关键在于理解内层while循环将左子节点全部入栈然后逐个处理。3. 对称二叉树判断3.1 递归解法对称二叉树要求左右子树镜像对称public boolean isSymmetric(TreeNode root) { return root null || 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; return left.val right.val isMirror(left.left, right.right) isMirror(left.right, right.left); }3.2 迭代解法使用队列进行层序遍历public boolean isSymmetric(TreeNode root) { if (root null) return true; QueueTreeNode queue new LinkedList(); queue.offer(root.left); queue.offer(root.right); while (!queue.isEmpty()) { TreeNode left queue.poll(); TreeNode right queue.poll(); if (left null right null) continue; if (left null || right null || left.val ! right.val) return false; queue.offer(left.left); queue.offer(right.right); queue.offer(left.right); queue.offer(right.left); } return true; }实际测试发现对于完全对称的大树迭代解法通常比递归更快因为避免了递归调用的开销。4. 二叉树的最大深度计算4.1 递归解法public int maxDepth(TreeNode root) { if (root null) return 0; return 1 Math.max(maxDepth(root.left), maxDepth(root.right)); }4.2 迭代解法BFSpublic int maxDepth(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; }5. 买卖股票的最佳时机虽然题目分类不同但这也是力扣经典问题public int maxProfit(int[] prices) { if (prices null || prices.length 0) return 0; int minPrice prices[0]; int maxProfit 0; for (int i 1; i prices.length; i) { if (prices[i] minPrice) { minPrice prices[i]; } else { maxProfit Math.max(maxProfit, prices[i] - minPrice); } } return maxProfit; }这个解法的时间复杂度是O(n)空间复杂度是O(1)。关键在于维护一个当前最小值并在遍历过程中不断计算可能的利润。6. 常见问题与优化技巧6.1 二叉树遍历中的空指针问题在实现二叉树算法时空指针异常是最常见的错误。建议始终先检查节点是否为null对于递归解法确保基准条件正确处理null情况对于迭代解法确保栈/队列不为空时才执行pop/poll操作6.2 递归与迭代的选择递归解法通常代码更简洁但有以下缺点栈空间有限深度过大会导致栈溢出函数调用开销较大调试可能更困难迭代解法通常性能更好可以处理更大的树但代码可能更复杂6.3 Java实现中的优化使用LinkedList而非ArrayList作为结果容器如果频繁插入对于对称二叉树判断迭代解法中队列初始容量可以预估避免在循环中创建新对象6.4 边界条件测试务必测试以下特殊情况空树(null)只有根节点的树完全不平衡的树(如所有节点只有左子节点)大规模数据测试(验证性能)7. 实际应用场景这些二叉树算法在实际开发中有广泛应用数据库索引结构(如B树、B树)文件系统目录结构游戏中的决策树编译器中的语法分析树机器学习中的决策树算法理解这些基础算法有助于我们更好地设计和优化这些系统。比如数据库查询优化器需要高效遍历查询计划树文件系统需要快速判断目录结构的对称性等。