《剑指Offer》7. 重建二叉树

题目链接

牛客网

题目描述

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

解题思路

pre: 1 247 3568
in : 472 1 5386
每次只需要找到中间的根节点即可

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