力扣---剑指 Offer 07. 重建二叉树-JZTXT

输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。

假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

示例 1:

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]
示例 2:

Input: preorder = [-1], inorder = [-1]
Output: [-1]

限制：

0 <= 节点个数 <= 5000

注意：本题与主站 105 题重复：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/zhong-jian-er-cha-shu-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

利用二叉树前序遍历第一个总是头结点，加下来都是左节点，剩下的都是右节点。

中序遍历头结点前面的都是左节点，后面的都是右节点。可以将之分为两个小数组来做。

即：每次在中序数组中找和前序数组开头相同数字的节点，然后将之作为左节点，

不断递归即可。

有点乱，这两天状态也不太对，就这样吧，以后有机会了再整理思路写一写。

class Solution {
    int[] preorder;
    int[] inorder;
    Map<Integer, Integer> map;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        this.inorder = inorder;
        map = new HashMap<>();
        for (int i = 0; i < inorder.length; i ++) {
            map.put(inorder[i], i);
        }
        return buildTree(0, preorder.length, 0, preorder.length);
    }
//    将前序数组和中序数组通过二叉树前序遍历和中序遍历的特点，分割成两个较小的前序数组和中序数组。
    private TreeNode buildTree (int p, int p2, int left, int right) {
        if (p >= p2 || left >= right) {
            return null;
        }
        TreeNode res = new TreeNode(preorder[p]);
        int root = preorder[p];
        int index = map.get(root) - left;
        res.left = buildTree(p + 1, p + index + 1, left, left + index);
        res.right = buildTree(p + index + 1, preorder.length, left + index + 1, right);
        return res;
    }
}