题目描述

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

题目分析

前序遍历是 根结点 -> 左子树 -> 右子树，中序遍历是 左子树 -> 根结点 -> 右子树
1. 前序遍历的第一个元素即根结点
2. 根据根结点的值，将中序遍历划分为 左 和 右 两个区域
3. 根据左子树结点的个数，将前序遍历划分为 左 和 右 两个区域
4. 递归处理子树

Java

public TreeNode buildTree(int[] preorder, int[] inorder) {
    if (preorder.length == 0 || inorder.length == 0) {
        return null;
    }
    int rootValue = preorder[0];
    int index = 0;
    for (int i = 0; i < inorder.length; i++) {
        if (inorder[i] == rootValue) {
            index = i;
            break;
        }
    }
    TreeNode root = new TreeNode(rootValue);
    root.left = buildTree(Arrays.copyOfRange(preorder, 1, 1 + index), Arrays.copyOfRange(inorder, 0, index));
    root.right = buildTree(Arrays.copyOfRange(preorder, 1 + index, preorder.length), Arrays.copyOfRange(inorder, index + 1, inorder.length));
    return root;
}

Kotlin

fun buildTree(preorder: IntArray, inorder: IntArray): TreeNode? {
    if (preorder.isEmpty() || inorder.isEmpty()) {
        return null
    }
    val rootValue = preorder[0]
    val index = inorder.indexOf(rootValue)
    val root = TreeNode(rootValue)
    root.left = buildTree(preorder.copyOfRange(1, index + 1), inorder.copyOfRange(0, index))
    root.right =
        buildTree(preorder.copyOfRange(index + 1, inorder.size), inorder.copyOfRange(index + 1, preorder.size))

    return root
}