题目描述

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

分析

根节点肯定是前序遍历的第一个数,在中序遍历中根节点左面的是它的左子树,右面的是它的右子树,分左右递归创建就可以了

public class Solution {

    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        TreeNode node = null;
        if(pre.length!=0){
            node = reConstruct(pre, in, 0,pre.length - 1,0,in.length - 1);
        }
        return node;

    }

    public TreeNode reConstruct(int [] pre,int [] in,int preleft,int preright,
        int inleft,int inright) {
        //当到达边界条件时候返回null
        if(preleft > preright || inleft > inright)
           return null;
       //新建一个TreeNode
       TreeNode node = new TreeNode(pre[preleft]);
     //对中序数组进行输入边界的遍历
       for(int i = inleft; i<= inright; i++){
           if(pre[preleft] == in[i]){
              //重构左子树，注意边界条件
               node.left = reConstruct(pre, in, preleft+1, preleft+i-inleft, inleft, i-1);
               //重构右子树，注意边界条件
               node.right = reConstruct(pre, in, preleft+i+1-inleft, preright, i+1, inright);
           }
       }
       return node;
    }
}

测试

public class Client {

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] pre = new int[]{1,2,4,7,3,5,6,8};
        int[] in = new int[]{4,7,2,1,5,3,8,6};
        TreeNode node = solution.reConstructBinaryTree(pre, in);
        inOrder(node);
    }

    public static void inOrder(TreeNode node){
        if(node!=null){
        System.out.println(node.val);
        inOrder(node.left);
        inOrder(node.right);
        }else {
            return;
        }
    }
}