输入某二叉树的前序遍历和中序遍历结果,请重建该二叉树并输出其后续遍历结果。假设输入的前序遍历和中序遍历结果中都不含重复的数字。树节点定义如下:
class BinaryTreeNode{
int val;
BinaryTreeNode left;
BinaryTreeNode right;
public BinaryTreeNode(int val) {
this.val=val;
}
}
输入:1,2,4,7,3,5,6,8 //前序序列
4,7,2,1,5,3,8,6 //中序序列
输出:7,4,2,5,8,6,3,1 //后序序列
思路
- 前序与中序都由三部分【根、左、右】组成,不管哪种遍历方式,他们子树的大小都是一样的
- 前序:根节点、【左子树】、【右子树】
- 中序:【左子树】、根节点、【右子树】
- 前序遍历的第一个一定是根节点,因此我们可以先将其定下来;随后我们要寻找左子树和右子树的分界线,如何寻找呢?中序可以帮助我们
- 由于前序已经知道了根节点,因此中序只需要遍历数组,将根节点的值与数组元素逐一对比,如果相同的话,就可以定下分界点。根节点左边的元素都是属于左子树的
- 我们通过这个左子树的大小,就可以确定左子树在前序中的分界点,分别对数组中左子树与右子树的部分进行递归,当前节点的左边就是左子树,当前节点的右边就是右子树
- 当我们发现左边索引大于右边索引,说明出现越界,即当前的子树是空树,返回null
public static BinaryTreeNode buildTree(int arr1[], int left1, int right1, int arr2[], int left2, int right2) {
if ( left1 > right1) {
// 说明此时树中已经没有节点了,是一棵空树
return null;
}
// 前序遍历第一位一定为当前树根节点
BinaryTreeNode root = new BinaryTreeNode(arr1[left1]);
int count = 0; // 用于记录左子树大小
for (int i = left2; i <= right2; i++) {
if (arr2[i] == root.val) {
// 说明来到了中序的根节点位置,此时左边为左子树,右边为右子树
break;
} else {
count++;
}
}
// root的左边由左子树构成,根据已知条件传入分割后的前序,中序序列
root.left = buildTree(arr1, left1 + 1, left1 + count, arr2, left2, left2 + count - 1);
// root的右边由右子树构成,根据已知条件传入分割后的前序,中序序列
root.right = buildTree(arr1, left1 + count + 1, right1, arr2, left2 + count+1, right2);
// 当左右子树都构造完毕后,整棵树也构造完毕
return root;
}
//后序遍历
public static void postPrint(BinaryTreeNode root) {
if (root == null) {
return;
}
postPrint(root.left);
postPrint(root.right);
System.out.print(root.val + " ");
}
题目来源于《剑指Offer:名企面试官精讲经典编程题》



