分享一个大牛的人工智能教程。零基础!通俗易懂!风趣幽默!希望你也加入到人工智能的队伍中来!请轻击http://www.captainbed.net
package live.every.day.DataStructure.Tree.BinaryTree;
import java.util.Arrays;
import java.util.HashMap;
/**
* 题目:
* 通过先序和中序数组生成后序数组。
*
* 思路:
* 先设置后序数组最右边的值,再根据右子树和左子树的划分,从右到左依次设置好后序数组的全部位置。
*
* @author Created by LiveEveryDay
*/
public class GetPostArrayByPreOrderInOrder {
public static int[] getPostArray(int[] pre, int[] in) {
if (pre == null || in == null) {
return null;
}
int len = pre.length;
int[] post = new int[len];
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < len; i++) {
map.put(in[i], i);
}
setPos(pre, 0, len - 1, in, 0, len - 1, post, len - 1, map);
return post;
}
private static int setPos(int[] p, int pi, int pj, int[] n, int ni, int nj, int[] s, int si, HashMap<Integer, Integer> map) {
if (pi > pj) {
return si;
}
s[si--] = p[pi];
int i = map.get(p[pi]);
si = setPos(p, pj - nj + i + 1, pj, n, i + 1, nj, s, si, map);
return setPos(p, pi + 1, pi + i - ni, n, ni, i - 1, s, si, map);
}
public static void main(String[] args) {
int[] pre = {1, 2, 4, 5, 8, 9, 3, 6, 7};
int[] in = {4, 2, 8, 5, 9, 1, 6, 3, 7};
int[] post = getPostArray(pre, in);
System.out.printf("The post array is: %s", Arrays.toString(post));
}
}
// ------ Output ------
/*
The post array is: [4, 8, 9, 5, 2, 6, 7, 3, 1]
*/