企业官网建设流程全解析

一、题目描述

给定一棵二叉树的前序遍历preorder和中序遍历inorder，请还原这棵二叉树。题目保证数组中没有重复元素。

preorder = [3, 9, 20, 15, 7] inorder = [9, 3, 15, 20, 7]

构造结果如下：

3 / \ 9 20 / \ 15 7

关键是从两种遍历序列中确定根节点，并划分左右子树。

二、前序找根，中序分左右

先回顾遍历顺序：

前序遍历：根 -> 左 -> 右 中序遍历：左 -> 根 -> 右

前序遍历的第一个元素3是根节点。在中序遍历中找到3：

[9, 3, 15, 20, 7] ↑ 根节点

根节点左边的[9]属于左子树，右边的[15,20,7]属于右子树。左子树只有一个节点，因此可以同步划分前序遍历：

左子树：preorder = [9]，inorder = [9] 右子树：preorder = [20,15,7]，inorder = [15,20,7]

两个子问题与原问题结构相同，因此可以递归构造：

1. 从前序遍历中取出当前根节点；

2. 在中序遍历中找到根节点的位置；

3. 递归构造左子树；

4. 递归构造右子树。

三、完整 Java 代码

class Solution { public TreeNode buildTree(int[] preorder, int[] inorder) { int len = preorder.length; if (len == 0) { return null; } TreeNode root = new TreeNode(preorder[0]); // 找到根节点在中序遍历中的索引位置,这个值也是左子树的所有元素个数 int rootInInorder = indexOf(inorder, preorder[0]); // 前序遍历中左子树的部分和右子树的部分 int[] preLeft = Arrays.copyOfRange(preorder, 1, 1 + rootInInorder); // 复制是左闭右开区间 int[] preRight = Arrays.copyOfRange(preorder, 1 + rootInInorder, len); // 中序遍历中左子树的部分和右子树的部分 int[] inLeft = Arrays.copyOfRange(inorder, 0, rootInInorder); int[] inRight = Arrays.copyOfRange(inorder, 1 + rootInInorder, len); // 递归构建左右子树 root.left = buildTree(preLeft, inLeft); root.right = buildTree(preRight, inRight); return root; } // 返回 x 在 a 中的下标，保证 x 一定在 a 中 private int indexOf(int[] a, int x) { for (int i = 0; ; i++) { if (a[i] == x) { return i; } } } }

四、常见错误

1. 把中序遍历的第一个元素当成根节点

根节点由前序遍历确定，中序遍历只负责划分左右区域。

2. 先构造右子树

全局指针按“根、左、右”移动，必须先递归左子树。

3. 区间没有排除根节点

正确边界为：

root.left = build(inorderLeft, rootIndex - 1); root.right = build(rootIndex + 1, inorderRight);