二叉树算法进阶：遍历、对称判断与路径计算实战-平芜编程栈

1. 项目概述：hot100-二叉树III的定位与价值

hot100-二叉树III是LeetCode高频算法题库中针对二叉树数据结构的进阶训练专题，主要涵盖二叉树遍历、对称性判断、路径计算等经典问题。作为程序员面试的必考题型，掌握这部分内容能显著提升解决复杂树形结构问题的能力。我在实际刷题和面试辅导中发现，二叉树类题目看似基础，但80%的候选人会在递归终止条件、空指针处理等细节翻车。

这个专题的典型特征是将基础算法（如前中后序遍历）与实际问题（如路径求和、子树判断）相结合，考察开发者对递归和迭代双重思维的理解。例如对称二叉树问题（LeetCode 101）就要求同时掌握层次遍历和镜像递归两种解法，这正是面试官最青睐的"一题多解"考察方式。

2. 核心算法原理深度解析

2.1 二叉树遍历的六种实现范式

二叉树遍历是解决所有衍生问题的基础，实际应用中需要根据场景灵活选择：

递归三件套（前序/中序/后序）

// 前序遍历模板 void traverse(TreeNode root) { if (root == null) return; // 处理当前节点 System.out.println(root.val); traverse(root.left); traverse(root.right); }

迭代法双栈技巧

// 后序遍历迭代实现 Deque<TreeNode> stack = new ArrayDeque<>(); stack.push(root); Deque<Integer> res = new ArrayDeque<>(); while (!stack.isEmpty()) { TreeNode node = stack.pop(); res.push(node.val); if (node.left != null) stack.push(node.left); if (node.right != null) stack.push(node.right); } // res中的顺序即为后序结果

关键经验：迭代法处理中序遍历时，需要配合指针和栈的协同操作，这是面试常考的难点

2.2 对称二叉树判断的三种视角

判断二叉树是否对称（LeetCode 101）至少有三种实现路径：

递归镜像法（最优时空复杂度）

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

层次遍历验证法

boolean isSymmetric(TreeNode root) { Queue<TreeNode> q = new LinkedList<>(); q.offer(root.left); q.offer(root.right); while (!q.isEmpty()) { TreeNode n1 = q.poll(); TreeNode n2 = q.poll(); if (n1 == null && n2 == null) continue; if (n1 == null || n2 == null || n1.val != n2.val) return false; q.offer(n1.left); q.offer(n2.right); q.offer(n1.right); q.offer(n2.left); } return true; }

翻转比较法（空间复杂度较高）

boolean isSymmetric(TreeNode root) { return isSameTree(root.left, mirror(root.right)); } TreeNode mirror(TreeNode root) { if (root == null) return null; TreeNode left = mirror(root.left); TreeNode right = mirror(root.right); root.left = right; root.right = left; return root; }

3. 高频问题实战解析

3.1 二叉树路径总和问题（LeetCode 112）

问题描述：判断是否存在从根节点到叶子节点的路径，使得节点值之和等于目标值。

解法要点：

递归终止条件必须判断是否为叶子节点（左右子节点均为null）
注意负数节点值的存在可能改变剪枝策略
推荐使用目标值递减法避免额外变量存储路径和

boolean hasPathSum(TreeNode root, int targetSum) { if (root == null) return false; if (root.left == null && root.right == null) return root.val == targetSum; return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val); }

3.2 二叉树中的最大路径和（LeetCode 124）

进阶难点：

路径不一定经过根节点
需要同时考虑单边贡献值和全局最大值
使用类成员变量记录全局结果

class Solution { int maxSum = Integer.MIN_VALUE; public int maxPathSum(TreeNode root) { maxGain(root); return maxSum; } int maxGain(TreeNode node) { if (node == null) return 0; int leftGain = Math.max(maxGain(node.left), 0); int rightGain = Math.max(maxGain(node.right), 0); maxSum = Math.max(maxSum, node.val + leftGain + rightGain); return node.val + Math.max(leftGain, rightGain); } }

4. 工程实践中的优化技巧

4.1 避免递归栈溢出的迭代转换

当处理超深二叉树时（如链表化的极端情况），递归解法可能导致栈溢出。以中序遍历为例的迭代安全写法：

List<Integer> inorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<>(); Deque<TreeNode> stack = new ArrayDeque<>(); 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; }

4.2 二叉树序列化/反序列化的实用方案

在实际工程中（如分布式系统通信），常需要将二叉树结构转化为字符串传输。推荐使用层次遍历的紧凑格式：

// 序列化 String serialize(TreeNode root) { if (root == null) return "[]"; Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); StringBuilder sb = new StringBuilder("["); while (!queue.isEmpty()) { TreeNode node = queue.poll(); if (node != null) { sb.append(node.val).append(","); queue.offer(node.left); queue.offer(node.right); } else { sb.append("null,"); } } sb.setLength(sb.length() - 1); return sb.append("]").toString(); } // 反序列化 TreeNode deserialize(String data) { if (data.equals("[]")) return null; String[] vals = data.substring(1, data.length() - 1).split(","); TreeNode root = new TreeNode(Integer.parseInt(vals[0])); Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); int i = 1; while (!queue.isEmpty()) { TreeNode node = queue.poll(); if (!vals[i].equals("null")) { node.left = new TreeNode(Integer.parseInt(vals[i])); queue.offer(node.left); } i++; if (!vals[i].equals("null")) { node.right = new TreeNode(Integer.parseInt(vals[i])); queue.offer(node.right); } i++; } return root; }

5. 面试实战中的避坑指南

空指针防御：所有节点访问前必须判空，特别是左右子节点的检查
递归终止条件：叶子节点判断标准是node.left == null && node.right == null
路径类问题陷阱：注意题目要求的路径是否必须到达叶子节点
变量作用域：在递归解法中慎用类成员变量，避免多测试用例间的状态污染
测试用例设计：
- 空树
- 单节点树
- 完全左斜/右斜树
- 包含负值的树
- 超大深度树（测试栈溢出）

6. 性能优化关键指标

问题类型	时间复杂度	空间复杂度	优化方向
基本遍历	O(n)	O(h)递归栈	改为迭代降低栈深度
路径求和	O(n)	O(h)	提前终止递归
最大路径和	O(n)	O(h)	后序遍历计算单边贡献值
序列化/反序列化	O(n)	O(n)队列辅助空间	使用更紧凑的存储格式