二叉树构造：根据遍历序列的JAVA实现

"四种根据给定遍历序列构造二叉树的方法" 在计算机科学中，二叉树是一种数据结构，它由节点（或称为顶点）组成，每个节点最多有两个子节点，通常分为左子节点和右子节点。二叉树的遍历是访问所有节点的过程，常见的遍历方式有前序遍历、中序遍历和后序遍历。这些遍历方法对于理解和操作二叉树至关重要。本篇文章将重点讨论如何根据给定的遍历序列构造二叉树，具体包括四种情况：根据前序与中序遍历序列、先序遍历构造二叉搜索树、中序与后序遍历序列以及前序与后序遍历序列。 1. 根据前序与中序遍历序列构造二叉树 前序遍历的顺序是：根节点 -> 左子树 -> 右子树，中序遍历的顺序是：左子树 -> 根节点 -> 右子树。利用这两个序列可以唯一地恢复一棵二叉树。具体步骤如下： - 递归版（哈希表）： - 首先，前序遍历的第一个元素是根节点的值，存储在哈希表中以查找索引。 - 找到根节点在中序遍历序列中的索引`index`，`index`左边的元素构成左子树，右边的元素构成右子树。 - 递归地构建左子树（前序序列的第二个到`index`的元素，中序序列的左半部分）和右子树（前序序列的`index+1`到最后，中序序列的右半部分）。 ```java public TreeNode buildTree(int[] preorder, int[] inorder) { this.preorder = preorder; this.inorder = inorder; HashMap<Integer, Integer> indexMap = new HashMap<>(); for (int val : inorder) indexMap.put(val, idx++); return help(0, inorder.length); } public TreeNode help(int inLeft, int inRight) { if (inLeft == inRight) return null; int rootVal = preorder[preIndex++]; int index = indexMap.get(rootVal); TreeNode root = new TreeNode(rootVal); root.left = help(inLeft, index); root.right = help(index + 1, inRight); return root; } ``` 2. 根据先序遍历构造二叉搜索树 先序遍历的顺序是：根节点 -> 左子树 -> 右子树。由于二叉搜索树的特性，左子树上的所有节点都小于根节点，右子树上的所有节点都大于根节点。因此，每次构建节点时，可以保证当前节点的值是子序列中最大的（或最小的）值。 3. 根据中序与后序遍历序列构造二叉树 后序遍历的顺序是：左子树 -> 右子树 -> 根节点。结合中序遍历，可以找到根节点，然后递归地构建左右子树。 4. 根据前序与后序遍历序列构造二叉树 前序遍历的顺序是：根节点 -> 左子树 -> 右子树，后序遍历的顺序是：左子树 -> 右子树 -> 根节点。这个过程稍微复杂，因为没有中序遍历来直接确定根节点的位置。但通过分析两个序列，可以找到规律来构建树。 总结： 这四种方法都是基于二叉树的遍历特性来恢复二叉树结构。递归是常用且直观的解决方案，通过分割问题并逐层解决，直到构建出完整的二叉树。非递归方法，如使用栈，也可以实现，但理解起来可能更复杂。无论哪种方法，都需要对二叉树的遍历和递归有深入的理解。在实际编程中，根据具体场景选择合适的方法是关键。