在学习树的时候，碰到了一道题，是如何从先序遍历和中序遍历的结果中得到后序遍历，正常情况下第一反应就是重建二叉树，然后再后序输出，在室友的指点下发现可以通过对数组的操作得到结果，重点是如何把握好指向节点的位置
从先序或者后序结合中序得到后续或者先序或者层次序列比较容易，但是对于先序结合后序得到中序是有一定困难的，因为可能得到的树不是唯一的，所以在这里就不讨论这种情况
假设我们有一棵二叉树，各种遍历方式输出结果如下表所示
| 遍历\节点 | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| 先序遍历 | 1 | 2 | 3 | 4 | 5 | 6 |
| 中序遍历 | 3 | 2 | 4 | 1 | 6 | 5 |
| 后序遍历 | 3 | 4 | 2 | 6 | 5 | 1 |
| 层次遍历 | 1 | 2 | 5 | 3 | 4 | 6 |
/**
* 从先序中序获取后序
* @param preorder 先序序列
* @param inorder 中序序列
* @param root 根节点 初始值为0
* @param start 起始节点 初始值为0
* @param end 终止节点 初始值为preorder.length - 1
*/
public void PostorderFromPreorderInorder(int[] preorder, int[] inorder, int root, int start, int end) {
if (start > end) return;
int i = start;
while (i < end && inorder[i] != preorder[root]) i++; //让i指向中序遍历的根节点
PostorderFromPreorderInorder(preorder, inorder, root + 1, start, i - 1); //遍历左子树
PostorderFromPreorderInorder(preorder, inorder, root + i + 1 - start, i + 1, end); //遍历右子树
System.out.print(preorder[root] + " ");
}
/**
* 从中序后序获取先序
* @param inorder 中序序列
* @param postorder 后序序列
* @param root 根节点 初始值为postorder.length - 1
* @param start 起始节点 初始值为0
* @param end 终止节点 初始值为postorder.length - 1
*/
public void PreorderFromInorderPostorder(int[] inorder, int[] postorder, int root, int start, int end) {
if (start > end) return;
int i = start;
while (i < end && inorder[i] != postorder[root]) i++; //让i指向中序遍历的根节点
System.out.print(postorder[root] + " ");
PreorderFromInorderPostorder(inorder, postorder, root - 1 - end + i, start, i - 1); //遍历左子树
PreorderFromInorderPostorder(inorder, postorder, root - 1, i + 1, end); //遍历右子树
}
/**
* 从前序中序获取层次
* @param preorder 前序序列
* @param inorder 中序序列
* @param levelorder 存储层次序列结果
* @param root 根节点 初始值为preorder.length - 1
* @param start 起始节点 初始值为0
* @param end 终止节点 初始值为preorder.length - 1
* @param index 层次序列的指针 初始值为0
*/
public void LavelorderFromPreorderInorder(int[] preorder, int[] inorder, int[] levelorder, int root, int start, int end, int index) {
if (start > end) return;
int i = start;
while (i < end && inorder[i] != preorder[root]) i++;
levelorder[index] = preorder[root];
LavelorderFromPreorderInorder(preorder, inorder, levelorder, root + 1, start, i - 1, 2 * index + 1);
LavelorderFromPreorderInorder(preorder, inorder, levelorder, root + i + 1 - start, i + 1, end, 2 * index + 2);
}
/**
* 从中序后序获取层次
* @param inorder 中序序列
* @param postorder 后序序列
* @param levelorder 存储层次序列结果
* @param root 根节点 初始值为0
* @param start 起始节点 初始值为0
* @param end 终止节点 初始值为postorder.length - 1
* @param index 层次序列的指针 初始值为0
*/
public void LavelorderFromInorderPostorder(int[] inorder, int[] postorder, int[] levelorder, int root, int start, int end, int index) {
if (start > end) return;
int i = start;
while (i < end && inorder[i] != postorder[root]) i++;
levelorder[index] = postorder[root];
LavelorderFromInorderPostorder(inorder, postorder, levelorder, root - 1 - end + i, start, i - 1, 2 * index + 1);
LavelorderFromInorderPostorder(inorder, postorder, levelorder, root - 1, i + 1, end, 2 * index + 2);
}