根据前序遍历和中序遍历结果重构二叉树

力扣原题链接：剑指 Offer 07. 重建二叉树 - 力扣（LeetCode） (leetcode-cn.com)

思路

中序遍历结果为左子树->根结点->右子树

由此我们可以确定树的范围，左子树范围为[0,根结点），根结点，（根结点，中序遍历结果数组长度-1]

再根据前序遍历结果确定根结点位置，前序遍历结果为根结点->左子树->右子树

然后递归就行了

递归出口为：当树范围的左边界大于右边界时，说明该结点为null结点

代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    // 前序遍历结果
    int[] preorder;
    // 存放结点位置，用于确定子树边界
    HashMap<Integer, Integer> map = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        // 前序遍历结果
        this.preorder = preorder;
        // 存放结点位置
        for (int i = 0; i < inorder.length; i++) {
            // Map<结点值，结点位置>
            map.put(inorder[i],i);
        }
        // 根结点根据前序遍历结果确定，左右边界根据中序遍历结果确定
        // 根结点为数组第一个元素，左边界为0，右边界为数组长度-1
        return build(0,0,preorder.length-1);
    }
    /**
    * 重构二叉树
    */
    public TreeNode build(int root,int left,int right){
        // 递归出口，说明该结点为null结点
        if (left>right){
            return null;
        }
        // 新建根结点
        TreeNode node = new TreeNode(preorder[root]);
        // 根据根结点确定子树边界
        int i = map.get(preorder[root]);
        // 根结点根据前序遍历结果确定，左右边界根据中序遍历结果确定
        // 根结点的 左子树的根结点为 前序遍历结果中 根结点的下一个结点
        // 左子树的边界分别为 根结点的左边界 和 中序遍历结果中根结点的前一个结点
        node.left = build(root+1,left,i-1);
        // 根结点的 右子树的根结点为 前序遍历结果中 （根结点+左子树）的下一个结点
        // 右子树的边界分别为 中序遍历结果中根结点的下一个结点 和 根结点的右边界
        node.right = build(root+1+i-left,i+1,right);
        // 返回根结点
        return node;
    }
}