package algorithm.swordtooffer;

/**

* @author 李文浩

* @version 2017/7/30.

* 输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

* 例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

* 思路

*/

public class Test6 {

public static class TreeNode {

int val;

TreeNode left;

TreeNode right;

TreeNode(int x) {

val = x;

}

}

public TreeNode reConstructBinaryTree(int[] pre, int[] in) {

if (pre == null || in == null || pre.length != in.length || in.length < 1) {

return null;

}

return construct(pre, 0, pre.length - 1, in, 0, in.length - 1);

// 下面是另一个更好的解法

// return reConstructBinaryTree(pre, 0, pre.length - 1, in, 0, in.length - 1);

}

public static TreeNode construct(int[] preorder, int ps, int pe, int[] inorder, int is, int ie) {

// 开始位置大于结束位置说明已经没有需要处理的元素了

if (ps > pe) {

return null;

}

// 取前序遍历的第一个数字，就是当前的根结点

int value = preorder[ps];

int index = is;

// 在中序遍历的数组中找根结点的位置

while (index <= ie && inorder[index] != value) {

index++;

}

// 如果在整个中序遍历的数组中没有找到，说明输入的参数是不合法的，抛出异常

if (index > ie) {

throw new RuntimeException("Invalid input");

}

// 创建当前的根结点，并且为结点赋值

TreeNode node = new TreeNode(value);

// 递归构建当前根结点的左子树，左子树的元素个数：index-is+1个

// 左子树对应的前序遍历的位置在[ps+1, ps+index-is]

// 左子树对应的中序遍历的位置在[is, index-1]

node.left = construct(preorder, ps + 1, ps + index - is, inorder, is, index - 1);

// 递归构建当前根结点的右子树，右子树的元素个数：ie-index个

// 右子树对应的前序遍历的位置在[ps+index-is+1, pe]

// 右子树对应的中序遍历的位置在[index+1, ie]

node.right = construct(preorder, ps + index - is + 1, pe, inorder, index + 1, ie);

// 返回创建的根结点

return node;

}

//前序遍历{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}

/**

* 大神级解法

*

* @param pre

* @param startPre

* @param endPre

* @param in

* @param startIn

* @param endIn

* @return

*/

private TreeNode reConstructBinaryTree(int[] pre, int startPre, int endPre, int[] in, int startIn, int endIn) {

if (startPre > endPre || startIn > endIn)

return null;

TreeNode root = new TreeNode(pre[startPre]);

for (int i = startIn; i <= endIn; i++)

if (in[i] == pre[startPre]) {

root.left = reConstructBinaryTree(pre, startPre + 1, startPre + i - startIn, in, startIn, i - 1);

root.right = reConstructBinaryTree(pre, i - startIn + startPre + 1, endPre, in, i + 1, endIn);

}

return root;

}

}