题目：
题解：
题解一：
在递归方法中，传入子数组的边界索引。
注意：在递归方法中，有一个数组的边界索引，得通过计算得到，计算的依据是递归方法传入的“中序遍历数组”（的子数组）和“后序遍历数组”（的子数组）的长度是一样的。我的办法是解方程计算未知数。具体需要计算哪个参数我在下面的代码中已经注明了。
下面展示了一个计算边界的方法。
例如：
2. 题解二：
可以把中序遍历的值和索引放在一个哈希表中，就不需要通过遍历得到当前根结点在中序遍历中的位置了。
3. 题解三：
后序的遍历顺序是，左右中
中序的遍历顺序是，左中右
1.根据后序建立索引，从后往前一个一个拿出来，首先拿出最后一个数a，然后找到中序里a的位置
2.中序里面a左边的就是左子树，a右边的就是右子树，递归调用就行了
4. 题解四：
目标：如何从中序与后序遍历序列构造二叉树
分析：这一类题需要我们把中序链表放入 map 中，根据后序的顺序来递归出每个节点的左子树和右子树
错误：这题需要先遍历右子树再遍历左子树，不要乱顺序
关键：以中序为基础，以后序链表从后往前的顺序构建出每个节点的左子树和右子树
代码：
1. 代码一：
/** * code106 */
public class code106 {
public static TreeNode buildTree(int[] inorder, int[] postorder) {
int inLen = inorder.length;
int postLen = postorder.length;
return build(inorder, 0, inLen - 1, postorder, 0, postLen - 1);
}
/** * 使用中序遍历序列 inorder 的子区间 [inLeft, inRight] 与后序遍历序列 postorder 的子区间 [postLeft, * postRight] 构建二叉树 * * @param inorder 中序遍历序列 * @param inLeft 中序遍历序列的左边界 * @param inRight 中序遍历序列的右边界 * @param postorder 后序遍历序列 * @param postLeft 后序遍历序列的左边界 * @param postRight 后序遍历序列的右边界 * @return 二叉树的根结点 */
public static TreeNode build(int inorder[], int inLeft, int inRight, int postorder[], int postLeft, int postRight) {
if (inLeft > inRight || postLeft > postRight) {
return null;
}
int pivot = postorder[postRight];
int pivotIndex = inLeft;
while (inorder[pivotIndex] != pivot) {
pivotIndex++;
}
TreeNode root = new TreeNode(pivot);
root.left = build(inorder, inLeft, pivotIndex - 1, postorder, postLeft, postRight - inRight + pivotIndex - 1);
root.right = build(inorder, pivotIndex + 1, inRight, postorder, postRight - inRight + pivotIndex,
postRight - 1);
return root;
}
public static void main(String[] args) {
int inorder[] = { 9, 3, 15, 20, 7 };
int postorder[] = { 9, 15, 7, 20, 3 };
TreeNode tree = buildTree(inorder, postorder);
System.out.println("***************************************");
TreeOperation.show(tree);
System.out.println("***************************************");
}
}
2. 代码二：
/** * code106 */
import java.util.*;
public class code106 {
public static TreeNode buildTree(int[] inorder, int[] postorder) {
int inLen = inorder.length;
int postLen = postorder.length;
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < inLen; i++) {
map.put(inorder[i], i);
}
return build(0, inLen - 1, postorder, 0, postLen - 1, map);
}
/** * 使用中序遍历序列 inorder 的子区间 [inLeft, inRight] 与后序遍历序列 postorder 的子区间 [postLeft, * postRight] 构建二叉树 * * @param inLeft 中序遍历序列的左边界 * @param inRight 中序遍历序列的右边界 * @param postLeft 后序遍历序列的左边界 * @param postRight 后序遍历序列的右边界 * @return 二叉树的根结点 */
public static TreeNode build(int inLeft, int inRight, int postorder[], int postLeft, int postRight,
Map<Integer, Integer> map) {
if (inLeft > inRight || postLeft > postRight) {
return null;
}
int pivot = postorder[postRight];
int pivotIndex = map.get(pivot);
TreeNode root = new TreeNode(pivot);
root.left = build(inLeft, pivotIndex - 1, postorder, postLeft, postRight - inRight + pivotIndex - 1, map);
root.right = build(pivotIndex + 1, inRight, postorder, postRight - inRight + pivotIndex, postRight - 1, map);
return root;
}
public static void main(String[] args) {
int inorder[] = { 9, 3, 15, 20, 7 };
int postorder[] = { 9, 15, 7, 20, 3 };
TreeNode tree = buildTree(inorder, postorder);
System.out.println("***************************************");
TreeOperation.show(tree);
System.out.println("***************************************");
}
}
3. 代码三：
/** * code106 */
import java.util.*;
public class code106 {
// 解法三：
public static int index;
public static TreeNode buildTree(int[] inorder, int[] postorder) {
index = postorder.length - 1;
return build(inorder, postorder, 0, inorder.length - 1);
}
public static TreeNode build(int inorder[], int postorder[], int inStart, int inEnd) {
if (inStart > inEnd) {
return null;
}
int val = postorder[index--];
for (int i = inStart; i <= inEnd; i++) {
if (inorder[i] == val) {
TreeNode root = new TreeNode(val);
root.right = build(inorder, postorder, i + 1, inEnd);
root.left = build(inorder, postorder, inStart, i - 1);
return root;
}
}
return null;
}
public static void main(String[] args) {
int inorder[] = { 9, 3, 15, 20, 7 };
int postorder[] = { 9, 15, 7, 20, 3 };
TreeNode tree = buildTree(inorder, postorder);
System.out.println("***************************************");
TreeOperation.show(tree);
System.out.println("***************************************");
}
}
4. 代码四：
/** * code106 */
import java.util.*;
public class code106 {
// 解法四：
public static int pindex;// 后序的索引
public static TreeNode buildTree(int[] inorder, int[] postorder) {
pindex = postorder.length - 1;// 因为二叉树的第一个节点对应后序的最后一个，从最后一个开始
Map<Integer, Integer> map = new HashMap<>();// 存放中序的映射
for (int i = 0; i < inorder.length; i++) {
map.put(inorder[i], i);
}
return build(postorder, 0, inorder.length - 1, map);
}
/** * * @param postorder 后序链表 * @param inLeft 中序的左边界 * @param inRight 中序的右边界 * @return 二叉树节点 */
public static TreeNode build(int postorder[], int inLeft, int inRight, Map<Integer, Integer> map) {
if (inLeft > inRight) {
return null;
}
int val = postorder[pindex--];// 从最后一个开始初始化为TreeNode
TreeNode root = new TreeNode(val);
int index = map.get(val);// 得到在中序的索引
root.right = build(postorder, index + 1, inRight, map);// 先遍历右子树
root.left = build(postorder, inLeft, index - 1, map);// 再遍历左子树
return root;
}
public static void main(String[] args) {
int inorder[] = { 9, 3, 15, 20, 7 };
int postorder[] = { 9, 15, 7, 20, 3 };
TreeNode tree = buildTree(inorder, postorder);
System.out.println("***************************************");
TreeOperation.show(tree);
System.out.println("***************************************");
}
}
京公网安备 11010502036488号