树的统一迭代法是一种比较通用的遍历方法,通过标记法来实现前序、中序、后序遍历,核心思想是通过栈中加入空指针来标记访问节点和处理节点的时机
树的递归遍历
递归遍历比较简单,只要完成模板,更改添加元素的位置代码,就可以轻松实现遍历顺序的调整
class Solution {public List<Integer> treeTraversal(TreeNode root) {// 创建结果列表,用于存储遍历结果List<Integer> result = new ArrayList<>();// 调用递归遍历方法,从根节点开始遍历traversal(root, result);// 返回完整的遍历结果return result;}/*** 递归遍历二叉树的核心方法* 通过调整三行代码的顺序,可以实现前序、中序、后序遍历* * @param root 当前遍历的节点* @param result 存储遍历结果的列表*/public void traversal(TreeNode root, List<Integer> result) {// 递归终止条件:当前节点为空,直接返回if (root == null) {return;}// ========== 前序遍历:中 -> 左 -> 右 ==========// 先访问当前节点(中)result.add(root.val); // 递归遍历左子树(左)traversal(root.left, result);// 递归遍历右子树(右)traversal(root.right, result);}
}
三种遍历的对比
前序遍历(中左右)
result.add(root.val); // 中
traversal(root.left, result); // 左
traversal(root.right, result); // 右
中序遍历(左中右)
traversal(root.left, result); // 左
result.add(root.val); // 中
traversal(root.right, result); // 右
后序遍历(左右中)
traversal(root.left, result); // 左
traversal(root.right, result); // 右
result.add(root.val); // 中
复杂度分析
时间复杂度 O(n)
- n 二叉树中的节点总数
- 每个节点只被访问一次:递归函数对每个节点恰好调用一次
- 常数时间操作:每个节点的处理(
result.add()
)是 O(1) 操作 - 总时间复杂度:n 个节点 × O(1) = O(n)
空间复杂度 O(h)
- h 二叉树的高度
- 递归调用栈的空间:
- 最坏情况:当树退化为链表时,h = n,空间复杂度为 O(n)
- 最好情况:当树是平衡二叉树时,\(h = log_2{n}\),空间复杂度为 O(log n)
- 平均情况:O(h),其中 h 是树的高度
树的统一迭代法
- 普通节点:需要遍历的节点
- 空节点:作为标记,表示下一个节点应该被处理加入结果集
public List<Integer> treeTraversal(TreeNode root) {// 创建结果列表,用于存储遍历结果List<Integer> result = new ArrayList<>();// 创建栈,用于模拟递归调用栈Stack<TreeNode> st = new Stack<>();// 如果根节点不为空,将其压入栈中开始遍历if (root != null) {st.push(root);}// 循环遍历直到栈为空while (!st.isEmpty()) {// 查看栈顶元素,但不弹出(peek操作)TreeNode node = st.peek();if (node != null) {// ========== 访问阶段 ==========// 当前节点不为空,说明是待访问的节点// 弹出当前节点,为重新组织访问顺序做准备st.pop();// ========== 前序遍历访问顺序:右 -> 左 -> 中 ==========// 栈是LIFO(后进先出),所以入栈顺序与遍历顺序相反// 如果右子节点不为空,将右子节点压入栈中if (node.right != null) {st.push(node.right); // 右子节点}// 如果左子节点不为空,将左子节点压入栈中if (node.left != null) {st.push(node.left); // 左子节点}// 将当前节点重新压入栈中st.push(node); // 当前节点(中)// 压入空节点作为标记,表示这个节点已经被访问过但还没有被处理// 当后续遇到这个空标记时,就知道下一个节点应该被处理(加入结果集)st.push(null); // 空标记} else {// ========== 处理阶段 ==========// 当前节点为空,说明遇到了之前设置的空标记// 空标记的下一个节点就是应该被处理的节点// 弹出空标记节点(当前栈顶的null)st.pop();// 查看栈顶元素(真正要处理的节点)node = st.peek();// 弹出要处理的节点st.pop();// 将节点的值加入结果列表,就是"处理"节点的操作result.add(node.val);}}// 返回遍历结果return result;
}
三种遍历的对比
前序遍历(中左右)
// 访问顺序:右 -> 左 -> 中
if (node != null) {st.pop();if (node.right != null) st.push(node.right); // 右if (node.left != null) st.push(node.left); // 左 st.push(node); // 中st.push(null);
}
中序遍历(左中右)
// 访问顺序:右 -> 中 -> 左
if (node != null) {st.pop();if (node.right != null) st.push(node.right); // 右st.push(node); // 中st.push(null);if (node.left != null) st.push(node.left); // 左
}
后序遍历(左右中)
// 访问顺序:中 -> 右 -> 左
if (node != null) {st.pop();st.push(node); // 中st.push(null);if (node.right != null) st.push(node.right); // 右if (node.left != null) st.push(node.left); // 左
}
复杂度分析
时间复杂度 O(n)
- n 二叉树中的节点总数
- 每个节点被处理两次:每个节点经历一次"访问阶段"(入栈和标记)和一次"处理阶段"(加入结果集)
- 常数时间操作:每个栈操作(push/pop/peek)和列表添加操作都是 O(1)
- 总时间复杂度:n 个节点 × 常数次操作 = O(n)
空间复杂值 O(n)
- 栈的空间使用:
- 最坏情况:当树退化为链表时,栈中同时存储约 2n 个元素(节点和空标记),空间复杂度为 O(n)
- 最好情况:当树是平衡二叉树时,栈的最大深度约为 \(2 \times log_2{n}\),空间复杂度为 O(log n)
- 平均情况:O(h),其中 h 是树的高度
- 结果列表的空间:必须存储所有 n 个节点的值,空间复杂度为 O(n)
- 总空间复杂度:栈空间 O(h) + 结果列表 O(n) = O(n)