题目链接

牛客网

题目描述

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

解题思路

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;
    }
    
}

// 缓存中序遍历数组每个值对应的索引
private Map<Integer, Integer> indexForInOrders = new HashMap<>();

public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
   
    for (int i = 0; i < in.length; i++)
        indexForInOrders.put(in[i], i);
    return reConstructBinaryTree(pre, 0, pre.length - 1, 0);
}

private TreeNode reConstructBinaryTree(int[] pre, int preL, int preR, int inL) {
   
    if (preL > preR)
        return null;
    TreeNode root = new TreeNode(pre[preL]);
    int inIndex = indexForInOrders.get(root.val);
    int leftTreeSize = inIndex - inL;
    root.left = reConstructBinaryTree(pre, preL + 1, preL + leftTreeSize, inL);
    root.right = reConstructBinaryTree(pre, preL + leftTreeSize + 1, preR, inL + leftTreeSize + 1);
    return root;
}