：通过先序和中序数组生成后序数组思路假设有

问题描述

Burk：从前序数组和中序数组生成后序数组

思考

假设一棵二叉树

前序遍历的结果是

中序遍历的结果是

因为前序遍历的大调度逻辑是，先左后右

后序遍历的调度逻辑是：先左，后右，后头。

所以：后序遍历的最后一个节点一定是前序遍历的头节点。

定义递归函数

// 先序遍历数组pre的[l1...r1]区间
// 中序遍历数组in的[l2...r2]区间
// 生成后序遍历数组pos的[l3...r3]区间
void func(int[] pre, int l1, int r1, int[] in, int l2, int r2, int[] pos, int l3, r3)

根据以上推论，可以得出以下结论

// 后序遍历的最后一个节点，一定是先序遍历的头节点

pos[r3] = pre[l1];

那么，在有序数组中，我们就可以定位到头节点的位置，也就是下图中标为黄色的位置，假设这个位置是index，

该索引将有序数组分为左右两部分。由于中序遍历的调度过程是：先left，然后head，然后right，所以在有序遍历[l2……index]区间内，是以索引位置为首的左树的有序遍历。假设[l2……index]区间的元素个数为b，那么在前序遍历中，从头开始计数b个元素，即：[l1……l1+b] 构成以索引位置为首的左树的前序遍历结果。

	public static void func(int[] pre, int l1, int r1, int[] in, int l2, int r2, int[] pos, int l3, int r3) {
		if (l1 > r1) {
			// 避免了无效情况
			return;
		}
		if (l1 == r1) {
			// 只有一个数的时候
			pos[l3] = pre[l1];
		} else {
			// 不止一个数的时候
			pos[r3] = pre[l1];
			// index表示某个头在中序数组中的位置
			int index;
			for (index = l2; index 
					break;
				}
			}
			int b = index - l2;
            // 构造左树
			func(pre, l1 + 1, l1 + b, in, l2, index - 1, pos, l3, l3 + b - 1);
		   // 构造右树
            func(pre, l1 + b + 1, r1, in, index + 1, r2, pos, l3 + b, r3 - 1);
		}
	}

优化

在递归函数func中，有一个遍历行为，

			for (index = l2; index <= r2; index++) {
				if (in[index] == pre[l1]) {
					break;
				}
			}

如果每次递归都得遍历，效率会降低，所以可以在开头设置一个map来存储中序遍历中每个值的位置信息，这样就不用遍历了查找位置，方法如下：

		Map map = new HashMap();
		for (int i = 0; i < n; i++) {
			inOrder[i] = in.nextInt();
			map.put(inOrder[i], i);
		}

这样预处理之后，每个索引的位置就不用遍历了，就

			int index = map.get(pre[l1]);

可以，看完整代码

import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int[] preOrder = new int[n];
		int[] inOrder = new int[n];
		for (int i = 0; i 
		}
		Map map = new HashMap();
		for (int i = 0; i < n; i++) {
			inOrder[i] = in.nextInt();
			map.put(inOrder[i], i);
		}
		int[] posOrder = new int[n];
		func(preOrder, 0, n - 1, inOrder, 0, n - 1, posOrder, 0, n - 1, map); 
		for (int i = 0; i < n; i++) {
			System.out.print(posOrder[i] + " ");
		}
		in.close();
	}
	public static void func(int[] pre, int l1, int r1, int[] in, int l2, int r2, int[] pos, int l3, int r3,
			Map map) {
		if (l1 > r1) {
			// 避免了无效情况
			return;

		}
		if (l1 == r1) {
			// 只有一个数的时候
			pos[l3] = pre[l1];
		} else {
			// 不止一个数的时候
			pos[r3] = pre[l1];
			// index表示某个头在中序数组中的位置
			int index = map.get(pre[l1]);
			int b = index - l2;
			func(pre, l1 + 1, l1 + b, in, l2, index - 1, pos, l3, l3 + b - 1, map);
			func(pre, l1 + b + 1, r1, in, index + 1, r2, pos, l3 + b, r3 - 1, map);
		}
	}
}

更多

算法和数据结构注释