剑指offer----重建二叉树

题目输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

我的解法：

public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        return fun(pre, in, 0, pre.length,0 ,in.length -1 );
    }
    private TreeNode fun(int[] pre, int[] in, int preLeftIndex,int preRightIndex, int inLeftIndex, int inRightIndex){
        if(inLeftIndex > inRightIndex   || preLeftIndex  > preRightIndex){
            return null;
        }
        TreeNode root = new TreeNode(pre[preLeftIndex]);
        for(int i = inLeftIndex; i <= inRightIndex; i++){
            if(in[i] == pre[preLeftIndex]){
                root.left = fun(pre, in, preLeftIndex + 1, preLeftIndex + i - inLeftIndex, inLeftIndex, i - 1 );
                root.right = fun(pre, in, preLeftIndex + i - inLeftIndex + 1, preRightIndex,i + 1, inRightIndex);
                break;
            }
        }
        return root;
    }
}

思路：

二叉树的前序遍历和中序遍历

• 前序遍历：先访问当前节点，然后以前序访问左子树，右子树。
• 中序遍历：先以中序遍历左子树，接着访问当前节点，然后以中序遍历右子树。

所以前序遍历的特点为：前序遍历的每一个节点都是当前子树的根节点，同时，以中序遍历中该节点为边界，可以把中序遍历的结果分为左子树和右子树

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

前序遍历的第一个节点将中序遍历的结果分成了{4,7,2}和{5,3,8,6}两部分，他就是以1为根的左右两个子树的全部节点
然后接着将其子树按照上述方法进行拆分，就可以获得原始的树结构了。
注：此种解法要保证在树中无重复节点
几个需要注意的点：

• 边界检查
• 如过要想复原一颗二叉树，需要知道他的前/后序遍历+中序遍历 因为前序和后序本质上是一样的，只有应用两种性质不一致的方式才能复原二叉树。