题目描述

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

答案

import java.util.Arrays;
public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        if(pre.length==0||in.length==0){
            return null;
        }
        TreeNode treenode = new TreeNode(pre[0]);
        for(int i = 0;i<in.length;i++){
            if(pre[0]==in[i]){
                treenode.left = reConstructBinaryTree(Arrays.copyOfRange(pre,1,i+1),Arrays.copyOfRange(in,0,i));
                treenode.right = reConstructBinaryTree(Arrays.copyOfRange(pre,i+1,pre.length),Arrays.copyOfRange(in,i+1,in.length));
            }
        }
        return treenode;
    }
}

解析

简单的二叉树概念考察,依旧是熟悉的递归调用。
前序:根左右
中序:左根右
后序:左右根

根据前序和中序可以得到数的结构,具体算法就是先通过前序确定根结点,然后通过中序确定左侧和右侧结点。

将左侧和右侧的结点分别变成新的前序和中序重新递归,将左侧的结点重新当成新的一个二叉树,找出新的根节点,再重复以上步骤。


醉后不知天在水,满船清梦压星河