国家电网Java面试被问：二叉树的前序、中序、后序遍历

一、核心概念与区别

1. 三种遍历的直观理解

java

// 二叉树节点定义 class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } /* 1 / \ 2 3 / \ \ 4 5 6 遍历顺序： - 前序 (Preorder)： 根 → 左 → 右 - 中序 (Inorder)： 左 → 根 → 右 - 后序 (Postorder)： 左 → 右 → 根 */

2. 遍历结果示例

java

public class TraversalResults { /* 示例二叉树： A / \ B C / \ \ D E F 遍历结果： 前序：A → B → D → E → C → F 中序：D → B → E → A → C → F 后序：D → E → B → F → C → A */ }

二、递归实现（基础）

1. 前序遍历（根-左-右）

java

class Solution { // 递归实现 public List<Integer> preorderTraversal(TreeNode root) { List<Integer> result = new ArrayList<>(); preorder(root, result); return result; } private void preorder(TreeNode node, List<Integer> list) { if (node == null) return; list.add(node.val); // 1. 访问根节点 preorder(node.left, list); // 2. 遍历左子树 preorder(node.right, list); // 3. 遍历右子树 } }

2. 中序遍历（左-根-右）

java

class Solution { // 递归实现 public List<Integer> inorderTraversal(TreeNode root) { List<Integer> result = new ArrayList<>(); inorder(root, result); return result; } private void inorder(TreeNode node, List<Integer> list) { if (node == null) return; inorder(node.left, list); // 1. 遍历左子树 list.add(node.val); // 2. 访问根节点 inorder(node.right, list); // 3. 遍历右子树 } }

3. 后序遍历（左-右-根）

java

class Solution { // 递归实现 public List<Integer> postorderTraversal(TreeNode root) { List<Integer> result = new ArrayList<>(); postorder(root, result); return result; } private void postorder(TreeNode node, List<Integer> list) { if (node == null) return; postorder(node.left, list); // 1. 遍历左子树 postorder(node.right, list); // 2. 遍历右子树 list.add(node.val); // 3. 访问根节点 } }

三、迭代实现（面试重点）

1. 前序遍历迭代实现

java

// 方法1：使用栈（推荐） public List<Integer> preorderTraversalIterative(TreeNode root) { List<Integer> result = new ArrayList<>(); if (root == null) return result; Deque<TreeNode> stack = new ArrayDeque<>(); 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; } // 方法2：模拟递归栈 public List<Integer> preorderTraversalIterative2(TreeNode root) { List<Integer> result = new ArrayList<>(); Deque<TreeNode> stack = new ArrayDeque<>(); TreeNode curr = root; while (curr != null || !stack.isEmpty()) { // 一路向左，访问并入栈 while (curr != null) { result.add(curr.val); // 访问 stack.push(curr); // 入栈，用于后续访问右子树 curr = curr.left; } // 转向右子树 curr = stack.pop().right; } return result; }

2. 中序遍历迭代实现

java

// 标准迭代实现 public List<Integer> inorderTraversalIterative(TreeNode root) { List<Integer> result = 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(); result.add(curr.val); // 访问根节点 // 转向右子树 curr = curr.right; } return result; }

篇幅限制下面就只能给大家展示小册部分内容了。整理了一份核心面试笔记包括了：Java面试、Spring、JVM、MyBatis、Redis、MySQL、并发编程、微服务、Linux、Springboot、SpringCloud、MQ、Kafc

需要全套面试笔记及答案
【点击此处即可/免费获取】​​​

3. 后序遍历迭代实现（难点）

java

// 方法1：使用两个栈（最易理解） public List<Integer> postorderTraversalTwoStacks(TreeNode root) { List<Integer> result = new ArrayList<>(); if (root == null) return result; Deque<TreeNode> stack1 = new ArrayDeque<>(); Deque<TreeNode> stack2 = new ArrayDeque<>(); stack1.push(root); // stack1 用于模拟"根-右-左"（前序变种） while (!stack1.isEmpty()) { TreeNode node = stack1.pop(); stack2.push(node); // 压入stack2 // 注意：左孩子先入栈，保证右孩子先被处理 if (node.left != null) { stack1.push(node.left); } if (node.right != null) { stack1.push(node.right); } } // stack2 出栈顺序即为"左-右-根" while (!stack2.isEmpty()) { result.add(stack2.pop().val); } return result; } // 方法2：使用一个栈 + 记录前驱节点（优化空间） public List<Integer> postorderTraversalOneStack(TreeNode root) { List<Integer> result = new ArrayList<>(); if (root == null) return result; Deque<TreeNode> stack = new ArrayDeque<>(); TreeNode curr = root; TreeNode lastVisited = null; // 记录上次访问的节点 while (curr != null || !stack.isEmpty()) { // 一路向左入栈 while (curr != null) { stack.push(curr); curr = curr.left; } TreeNode peekNode = stack.peek(); // 如果右子树存在且未被访问，转向右子树 if (peekNode.right != null && peekNode.right != lastVisited) { curr = peekNode.right; } else { // 否则，访问当前节点 result.add(peekNode.val); lastVisited = stack.pop(); } } return result; } // 方法3：前序遍历的逆序（技巧性） public List<Integer> postorderTraversalReverse(TreeNode root) { List<Integer> result = new ArrayList<>(); if (root == null) return result; Deque<TreeNode> stack = new ArrayDeque<>(); stack.push(root); // 执行"根-右-左"的遍历（前序遍历变种） while (!stack.isEmpty()) { TreeNode node = stack.pop(); result.add(node.val); // 注意：先左后右入栈，保证出栈时先右后左 if (node.left != null) { stack.push(node.left); } if (node.right != null) { stack.push(node.right); } } // 反转结果，得到"左-右-根" Collections.reverse(result); return result; }

四、Morris 遍历（O(1)空间）

1. Morris 前序遍历

java

public List<Integer> preorderTraversalMorris(TreeNode root) { List<Integer> result = new ArrayList<>(); TreeNode curr = root; while (curr != null) { if (curr.left == null) { // 如果没有左子树，直接访问并转向右子树 result.add(curr.val); curr = curr.right; } else { // 找到当前节点的前驱节点（左子树的最右节点） TreeNode predecessor = curr.left; while (predecessor.right != null && predecessor.right != curr) { predecessor = predecessor.right; } if (predecessor.right == null) { // 第一次到达，建立线索并访问当前节点 predecessor.right = curr; result.add(curr.val); // 访问 curr = curr.left; } else { // 第二次到达，说明左子树已访问完，恢复树结构 predecessor.right = null; curr = curr.right; } } } return result; }

2. Morris 中序遍历

java

public List<Integer> inorderTraversalMorris(TreeNode root) { List<Integer> result = new ArrayList<>(); TreeNode curr = root; while (curr != null) { if (curr.left == null) { // 没有左子树，访问当前节点并转向右子树 result.add(curr.val); curr = curr.right; } else { // 找到前驱节点 TreeNode predecessor = curr.left; while (predecessor.right != null && predecessor.right != curr) { predecessor = predecessor.right; } if (predecessor.right == null) { // 建立线索 predecessor.right = curr; curr = curr.left; } else { // 恢复树结构并访问当前节点 predecessor.right = null; result.add(curr.val); curr = curr.right; } } } return result; }

3. Morris 后序遍历（较复杂）

java

public List<Integer> postorderTraversalMorris(TreeNode root) { List<Integer> result = new ArrayList<>(); TreeNode dummy = new TreeNode(0); // 虚拟头节点 dummy.left = root; TreeNode curr = dummy; while (curr != null) { if (curr.left == null) { curr = curr.right; } else { // 找到前驱节点 TreeNode predecessor = curr.left; while (predecessor.right != null && predecessor.right != curr) { predecessor = predecessor.right; } if (predecessor.right == null) { // 建立线索 predecessor.right = curr; curr = curr.left; } else { // 恢复树结构，并倒序输出从curr.left到predecessor的路径 reverseAdd(curr.left, predecessor, result); predecessor.right = null; curr = curr.right; } } } return result; } // 倒序添加节点值 private void reverseAdd(TreeNode from, TreeNode to, List<Integer> result) { reverse(from, to); TreeNode node = to; while (true) { result.add(node.val); if (node == from) break; node = node.right; } reverse(to, from); } // 反转链表（从from到to的右指针路径） private void reverse(TreeNode from, TreeNode to) { if (from == to) return; TreeNode prev = from; TreeNode curr = from.right; while (prev != to) { TreeNode next = curr.right; curr.right = prev; prev = curr; curr = next; } }

五、实战应用与面试题

1. 根据遍历结果重建二叉树

java

// 前序+中序重建二叉树 public TreeNode buildTreeFromPreIn(int[] preorder, int[] inorder) { Map<Integer, Integer> inorderMap = new HashMap<>(); for (int i = 0; i < inorder.length; i++) { inorderMap.put(inorder[i], i); } return buildPreIn(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1, inorderMap); } private TreeNode buildPreIn(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd, Map<Integer, Integer> inorderMap) { if (preStart > preEnd || inStart > inEnd) return null; TreeNode root = new TreeNode(preorder[preStart]); int inorderRootIndex = inorderMap.get(root.val); int leftSubtreeSize = inorderRootIndex - inStart; root.left = buildPreIn(preorder, preStart + 1, preStart + leftSubtreeSize, inorder, inStart, inorderRootIndex - 1, inorderMap); root.right = buildPreIn(preorder, preStart + leftSubtreeSize + 1, preEnd, inorder, inorderRootIndex + 1, inEnd, inorderMap); return root; } // 中序+后序重建二叉树 public TreeNode buildTreeFromInPost(int[] inorder, int[] postorder) { Map<Integer, Integer> inorderMap = new HashMap<>(); for (int i = 0; i < inorder.length; i++) { inorderMap.put(inorder[i], i); } return buildInPost(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1, inorderMap); } private TreeNode buildInPost(int[] inorder, int inStart, int inEnd, int[] postorder, int postStart, int postEnd, Map<Integer, Integer> inorderMap) { if (inStart > inEnd || postStart > postEnd) return null; TreeNode root = new TreeNode(postorder[postEnd]); int inorderRootIndex = inorderMap.get(root.val); int leftSubtreeSize = inorderRootIndex - inStart; root.left = buildInPost(inorder, inStart, inorderRootIndex - 1, postorder, postStart, postStart + leftSubtreeSize - 1, inorderMap); root.right = buildInPost(inorder, inorderRootIndex + 1, inEnd, postorder, postStart + leftSubtreeSize, postEnd - 1, inorderMap); return root; }

2. 验证二叉搜索树（BST）

java

// 方法1：中序遍历验证（BST的中序是有序的） public boolean isValidBST(TreeNode root) { Deque<TreeNode> stack = new ArrayDeque<>(); TreeNode curr = root; Integer prev = null; while (curr != null || !stack.isEmpty()) { while (curr != null) { stack.push(curr); curr = curr.left; } curr = stack.pop(); // 检查当前值是否大于前一个值 if (prev != null && curr.val <= prev) { return false; } prev = curr.val; curr = curr.right; } return true; } // 方法2：递归验证 public boolean isValidBSTRecursive(TreeNode root) { return validate(root, null, null); } private boolean validate(TreeNode node, Integer min, Integer max) { if (node == null) return true; if ((min != null && node.val <= min) || (max != null && node.val >= max)) { return false; } return validate(node.left, min, node.val) && validate(node.right, node.val, max); }

3. 二叉树序列化与反序列化

java

public class Codec { // 前序遍历序列化 public String serialize(TreeNode root) { StringBuilder sb = new StringBuilder(); serializeHelper(root, sb); return sb.toString(); } private void serializeHelper(TreeNode node, StringBuilder sb) { if (node == null) { sb.append("null,"); return; } sb.append(node.val).append(","); serializeHelper(node.left, sb); serializeHelper(node.right, sb); } // 前序遍历反序列化 public TreeNode deserialize(String data) { Deque<String> nodes = new LinkedList<>(Arrays.asList(data.split(","))); return deserializeHelper(nodes); } private TreeNode deserializeHelper(Deque<String> nodes) { String val = nodes.removeFirst(); if (val.equals("null")) return null; TreeNode node = new TreeNode(Integer.parseInt(val)); node.left = deserializeHelper(nodes); node.right = deserializeHelper(nodes); return node; } }

4. 二叉树层次遍历变种

java

// 之字形遍历（锯齿形遍历） public List<List<Integer>> zigzagLevelOrder(TreeNode root) { List<List<Integer>> result = new ArrayList<>(); if (root == null) return result; Deque<TreeNode> queue = new LinkedList<>(); queue.offer(root); boolean leftToRight = true; while (!queue.isEmpty()) { int levelSize = queue.size(); List<Integer> level = new ArrayList<>(); for (int i = 0; i < levelSize; i++) { TreeNode node = queue.poll(); if (leftToRight) { level.add(node.val); } else { level.add(0, node.val); // 逆序添加 } if (node.left != null) queue.offer(node.left); if (node.right != null) queue.offer(node.right); } result.add(level); leftToRight = !leftToRight; } return result; }

六、复杂度分析与选择建议

1. 时间复杂度对比

2. 面试回答要点

java

// 面试时应展示的知识点 public class InterviewPoints { /* 前序遍历： - 应用：树的复制、序列化、目录结构显示 - 特点：第一个元素是根节点 中序遍历： - 应用：二叉搜索树得到有序序列、表达式树求值 - 特点：BST的中序是有序的 后序遍历： - 应用：计算目录大小、释放树内存、表达式树计算 - 特点：最后一个元素是根节点 迭代实现关键： - 前序：访问时机在入栈前 - 中序：访问时机在出栈时 - 后序：最难，可看作"根-右-左"的逆序 Morris遍历： - 优点：O(1)空间 - 缺点：修改了树结构（临时），适合只读场景 */ }

3. 常见面试题变形

1. N叉树的前后序遍历（LeetCode 589, 590）

2. 二叉搜索树迭代器（LeetCode 173）

3. 验证前序遍历序列（LeetCode 255）

4. 二叉树中所有距离为K的节点（LeetCode 863）

5. 恢复二叉搜索树（LeetCode 99）

篇幅限制下面就只能给大家展示小册部分内容了。整理了一份核心面试笔记包括了：Java面试、Spring、JVM、MyBatis、Redis、MySQL、并发编程、微服务、Linux、Springboot、SpringCloud、MQ、Kafc

需要全套面试笔记及答案
【点击此处即可/免费获取】​​​

七、代码模板总结

通用迭代模板

java

// 二叉树遍历通用框架 public void traverse(TreeNode root) { // 初始化 Deque<TreeNode> stack = new ArrayDeque<>(); TreeNode curr = root; while (curr != null || !stack.isEmpty()) { // 处理左子树 while (curr != null) { // 前序：在这里访问 curr stack.push(curr); curr = curr.left; } curr = stack.pop(); // 中序：在这里访问 curr // 处理右子树 curr = curr.right; // 后序：需要额外的状态记录 } }

递归模板记忆口诀

java

/* 前序遍历：print -> left -> right 中序遍历：left -> print -> right 后序遍历：left -> right -> print 记忆口诀： 前序：我（根）在前面 中序：我（根）在中间 后序：我（根）在后面 */

总结：二叉树遍历是算法基础，必须熟练掌握递归、迭代、Morris三种实现。面试时不仅要能写出来，还要理解不同遍历方式的应用场景和复杂度分析。对于后序遍历的迭代实现要特别重视，这是常见难点。