Java实现二叉树重建算法（剑指offer题解）

在详细介绍这个面试题的知识点之前，我们首先要理解什么是二叉树，以及什么是前序遍历和中序遍历。二叉树是一种常见的数据结构，在计算机科学和许多算法中都有广泛的应用。它是一种每个节点最多有两个子节点的树结构，通常子节点被称作“左子节点”和“右子节点”。 前序遍历（Pre-order Traversal）是一种深度优先遍历二叉树的方式，在遍历过程中，我们首先访问根节点，然后访问左子树，最后访问右子树。中序遍历（In-order Traversal）则是另一种遍历方式，我们先访问左子树，然后访问根节点，最后访问右子树。对于任何一个节点来说，中序遍历的结果都是先遍历它的左子树，再访问该节点，最后遍历它的右子树。 现在我们来看这个问题的具体实现。题目要求我们根据给定的前序遍历和中序遍历序列重建二叉树。这是一个经典的算法问题，可以通过递归的方式解决。解决的思路是这样的： 1. 前序遍历的第一个元素总是树的根节点。 2. 在中序遍历中找到根节点的位置，这样就将中序遍历的序列分成了两部分，左边是左子树的中序遍历结果，右边是右子树的中序遍历结果。 3. 根据左子树和右子树的节点数量，在前序遍历序列中也可以划分出左子树和右子树的前序遍历序列。 4. 对左子树和右子树重复以上步骤，直到所有节点都被处理，这样整个树就被构建起来了。 Java代码实现这个算法的大概框架如下： ```java class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } public class Solution { private int preIndex = 0; private int[] preorder; private int[] inorder; private Map<Integer, Integer> inorderIndexMap = new HashMap<>(); public TreeNode buildTree(int[] preorder, int[] inorder) { this.preorder = preorder; this.inorder = inorder; // 构建中序遍历的哈希表用于快速定位根节点在中序遍历中的位置 for (int i = 0; i < inorder.length; i++) { inorderIndexMap.put(inorder[i], i); } return buildTree(0, inorder.length - 1); } private TreeNode buildTree(int left, int right) { if (left > right) { return null; } // 前序遍历的第一个节点就是根节点 int rootVal = preorder[preIndex++]; TreeNode root = new TreeNode(rootVal); // 在中序遍历中找到根节点的位置 int rootIndex = inorderIndexMap.get(rootVal); // 递归构建左子树和右子树 root.left = buildTree(left, rootIndex - 1); root.right = buildTree(rootIndex + 1, right); return root; } } ``` 在上面的代码中，我们首先定义了一个TreeNode类来表示二叉树的节点，然后在Solution类中定义了一个buildTree方法，它接收前序遍历和中序遍历的数组作为参数。我们使用一个哈希表来存储中序遍历中每个节点的索引，这能帮助我们在O(1)时间内找到根节点在中序遍历中的位置。preIndex变量用于在递归过程中跟踪当前访问的前序遍历中的节点。 在buildTree方法中，我们首先检查左边界是否大于右边界，如果是，说明这个子树已经全部构建完成，返回null。然后我们取出前序遍历的第一个节点作为根节点，找到这个根节点在中序遍历中的位置，从而确定左子树和右子树的范围，再递归地构建左子树和右子树。 通过这种方式，我们就可以根据给定的前序遍历和中序遍历序列重建出原始的二叉树。这不仅考察了应聘者对二叉树遍历算法的理解，也考察了递归思想的运用以及对数组操作的熟悉程度。 此题是《剑指offer》这本书中的一道典型面试题，针对这类问题，面试官往往会考察应聘者是否能够清晰地理解二叉树遍历的原理，以及能否灵活运用这些原理解决实际问题。通过分析和编码解决这类问题，可以展示应聘者扎实的数据结构基础和良好的编程能力。