题目：
题解：
1. 题解一：
抓住“前序遍历的第 1 个元素一定是二叉树的根结点”，不难写出代码。关键还是拿 LeetCode 上面的例子画一个图，思路就很清晰了。
前序遍历数组的第 11 个数（索引为 00）的数一定是二叉树的根结点，于是可以在中序遍历中找这个根结点的索引，然后把“前序遍历数组”和“中序遍历数组”分为两个部分，就分别对应二叉树的左子树和右子树，分别递归完成就可以了。
下面是一个具体的例子，演示了如何计算数组子区间的边界：
2. 题解二：
可以将中序遍历的值和索引存在一个哈希表中，这样就可以一下子找到根结点在中序遍历数组中的索引。
3. 题解三：
4. 题解四：
目标：如何从先序与中序遍历序列构造二叉树
分析：这一类题需要我们把中序链表放入 map 中，根据先序的顺序来递归出每个节点的左子树和右子树
错误：这题需要先遍历左子树再遍历右子树，不要乱顺序
关键：以中序为基础，以先序链表从前往后的顺序构建出每个节点的左子树和右子树
代码：
1. 代码一：
/** * code105 */
public class code105 {
public static TreeNode buildTree(int[] preorder, int[] inorder) {
int preLen = preorder.length;
int inLen = inorder.length;
return build(preorder, 0, preLen - 1, inorder, 0, inLen - 1);
}
/** * 使用数组 preorder 在索引区间 [preLeft, preRight] 中的所有元素 * 和数组 inorder 在索引区间 [inLeft, inRight] 中的所有元素构造二叉树 * * @param preorder 二叉树前序遍历结果 * @param preLeft 二叉树前序遍历结果的左边界 * @param preRight 二叉树前序遍历结果的右边界 * @param inorder 二叉树后序遍历结果 * @param inLeft 二叉树后序遍历结果的左边界 * @param inRight 二叉树后序遍历结果的右边界 * @return 二叉树的根结点 */
public static TreeNode build(int preorder[], int preLeft, int preRight, int inorder[], int inLeft, int inRight) {
// 因为是递归调用的方法，按照国际惯例，先写递归终止条件
if (preLeft > preRight || inLeft > inRight) {
return null;
}
// 先序遍历的起点元素很重要
int pivot = preorder[preLeft];
TreeNode root = new TreeNode(pivot);
int pivotIndex = inLeft;
// 严格上说还要做数组下标是否越界的判断 pivotIndex < inRight
while (inorder[pivotIndex] != pivot) {
pivotIndex++;
}
root.left = build(preorder, preLeft + 1, preLeft + pivotIndex - inLeft, inorder, inLeft, pivotIndex - 1);
root.right = build(preorder, preLeft + pivotIndex - inLeft + 1, preRight, inorder, pivotIndex + 1, inRight);
return root;
}
public static void main(String[] args) {
int preorder[] = { 3, 9, 20, 15, 7 };
int inorder[] = { 9, 3, 15, 20, 7 };
TreeNode tree = buildTree(preorder, inorder);
System.out.println("***************************************");
TreeOperation.show(tree);
System.out.println("***************************************");
}
}
2. 代码二：
/** * code105 */
import java.util.*;
public class code105 {
public static TreeNode buildTree(int[] preorder, int[] inorder) {
int preLen = preorder.length;
int inLen = inorder.length;
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < inLen; i++) {
map.put(inorder[i], i);
}
return build(preorder, 0, preLen - 1, 0, inLen - 1, map);
}
/** * 使用数组 preorder 在索引区间 [preLeft, preRight] 中的所有元素 和数组 inorder 在索引区间 [inLeft, * inRight] 中的所有元素构造二叉树 * * @param preorder 二叉树前序遍历结果 * @param preLeft 二叉树前序遍历结果的左边界 * @param preRight 二叉树前序遍历结果的右边界 * @param inorder 二叉树后序遍历结果 * @param inLeft 二叉树后序遍历结果的左边界 * @param inRight 二叉树后序遍历结果的右边界 * @return 二叉树的根结点 */
public static TreeNode build(int preorder[], int preLeft, int preRight, int inLeft, int inRight,
Map<Integer, Integer> map) {
// 因为是递归调用的方法，按照国际惯例，先写递归终止条件
if (preLeft > preRight || inLeft > inRight) {
return null;
}
// 先序遍历的起点元素很重要
int pivot = preorder[preLeft];
TreeNode root = new TreeNode(pivot);
int pivotIndex = map.get(pivot);
root.left = build(preorder, preLeft + 1, preLeft + pivotIndex - inLeft, inLeft, pivotIndex - 1, map);
root.right = build(preorder, preLeft + pivotIndex - inLeft + 1, preRight, pivotIndex + 1, inRight, map);
return root;
}
public static void main(String[] args) {
int preorder[] = { 3, 9, 20, 15, 7 };
int inorder[] = { 9, 3, 15, 20, 7 };
TreeNode tree = buildTree(preorder, inorder);
System.out.println("***************************************");
TreeOperation.show(tree);
System.out.println("***************************************");
}
}
3. 代码三：
/** * code105 */
import java.util.*;
public class code105 {
// 解法三：
public static int index;
public static TreeNode buildTree(int[] preorder, int[] inorder) {
index = 0;
return build(preorder, inorder, 0, inorder.length - 1);
}
public static TreeNode build(int preorder[], int inorder[], int inStart, int inEnd) {
if (inStart > inEnd) {
return null;
}
int val = preorder[index++];
for (int i = inStart; i <= inEnd; i++) {
if (inorder[i] == val) {
TreeNode root = new TreeNode(val);
root.left = build(preorder, inorder, inStart, i - 1);
root.right = build(preorder, inorder, i + 1, inEnd);
return root;
}
}
return null;
}
public static void main(String[] args) {
int preorder[] = { 3, 9, 20, 15, 7 };
int inorder[] = { 9, 3, 15, 20, 7 };
TreeNode tree = buildTree(preorder, inorder);
System.out.println("***************************************");
TreeOperation.show(tree);
System.out.println("***************************************");
}
}
4. 代码四：
/** * code105 */
import java.util.*;
public class code105 {
// 解法四：
public static int preIndex;// 前序的索引
public static TreeNode buildTree(int[] preorder, int[] inorder) {
preIndex = 0;// 因为二叉树的第一个节点对应前序的第一个，从第一个开始
Map<Integer, Integer> map = new HashMap<>();// 存放中序的映射
for (int i = 0; i < inorder.length; i++) {
map.put(inorder[i], i);
}
return build(preorder, 0, inorder.length - 1, map);
}
/** * * @param preorder 前序链表 * @param inLeft 中序的左边界 * @param inRight 中序的右边界 * @return 二叉树节点 */
public static TreeNode build(int preorder[], int inLeft, int inRight, Map<Integer, Integer> map) {
if (inLeft > inRight) {
return null;
}
int val = preorder[preIndex++];// 从第一个开始初始化为TreeNode
TreeNode root = new TreeNode(val);
int index = map.get(val);// 得到在中序的索引
root.left = build(preorder, inLeft, index - 1, map);// 再遍历左子树
root.right = build(preorder, index + 1, inRight, map);// 先遍历右子树
return root;
}
public static void main(String[] args) {
int preorder[] = { 3, 9, 20, 15, 7 };
int inorder[] = { 9, 3, 15, 20, 7 };
TreeNode tree = buildTree(preorder, inorder);
System.out.println("***************************************");
TreeOperation.show(tree);
System.out.println("***************************************");
}
}
京公网安备 11010502036488号