题目描述

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

思路

1.使用递归的思想求解。
2.二叉树前序遍历的第一个元素是根。
3.在中序遍历中找到根的位置，根左边的元素就是左子树，根右边的元素就是右子树。
4.递归执行函数，当前序或中序的数组元素个数为0时，结束递归。

Java代码实现

public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        return reConstructBinaryTree(pre,0,pre.length-1,in,0,in.length-1);
    }

    private TreeNode reConstructBinaryTree(int [] pre,int preStart,int preEnd,int [] in,int inStart,int inEnd) {
        //递归的结束条件
        if(preStart > preEnd || inStart > inEnd)
            return null;
        int i;
        //寻找根
        for (i = 0; i <= inEnd - inStart + 1 ; i++) {
            if(in[i+inStart] == pre[preStart]){
                break;
            }
        }
        TreeNode root = new TreeNode(pre[preStart]);
        root.left =reConstructBinaryTree(pre,preStart+1,preStart+i,in,inStart,inStart+i-1);
        root.right =reConstructBinaryTree(pre,preStart+i+1,preEnd,in,inStart+i+1,inEnd);
        return root;
    }
}