Java描述 LeetCode，105. Construct Binary Tree from Preorder and Inorder Traversal 从前序与中序遍历序列构造⼆叉树

Java描述 LeetCode，105. Construct Binary Tree from Preorder and Inorder Traversal 从前序与中序遍历序列构造⼆叉树

大家好，我是河海哥，专注于后端，如果可以的话，想做一名code designer而不是普通的coder，一起见证河海哥的成长，您的评论与赞是我的最大动力，如有错误还请不吝赐教，万分感谢。一起支持原创吧！纯手打有笔误还望谅解。

题解

☘️正如106题 后序+中序 构建一棵二叉树，按道理这里应该很快就能解决，我在分割数组的时候还是出现了问题，究其原因还是在，我的范围乱分割，一会用左边的子树长度，一会用右子树长度，导致最后很难搞，我也很难发现错在哪，所以以后必须统一用左子树的长度来进行数组的范围切分，并且遵从左闭区间，右闭区间的思路，而且有一个很关键的点，我画的是最简单的1 2 3，总是习惯性的用0去写死了范围，这很致命，以至于我栽跟头了，要知道，递归的时候，有preleft来标记左区间了，左区间不一定就是0啊！要命了。。

代码如下：

Map map = new HashMap<>();

public TreeNode buildTree(int[] preorder, int[] inorder) {
    if (preorder.length == 0) {
        return null;
    }
    for (int i = 0; i < inorder.length; i++) {
        map.put(inorder[i], i);
    }
    return traverse(preorder, inorder, 0, preorder.length - 1, 0, inorder.length - 1);
}

public TreeNode traverse(int[] preorder, int[] inorder, int preorderLeft, int preorderRight, int inorderLeft, int inorderRight) {
    if (preorderLeft > preorderRight) {
        return null;
    }

    int rootValue = preorder[preorderLeft];
    int rootIndex = map.get(rootValue);
    int leftSubtreeLength = rootIndex - inorderLeft;
    TreeNode root = new TreeNode(rootValue);
    root.left = traverse(preorder, inorder, preorderLeft + 1, preorderLeft + leftSubtreeLength, inorderLeft // 当时这里写的0, rootIndex - 1);
    root.right = traverse(preorder, inorder, preorderLeft + leftSubtreeLength + 1, preorderRight, rootIndex + 1, inorderRight);
    return root;
}