1.题目

输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。
假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
eg:

image.png

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/zhong-jian-er-cha-shu-lcof

2.解题

前序遍历（根在前面）：根左右
中序遍历（根在中间）：左右根
思路： 递归遍历，通过前序遍历找到根节点，然后递归遍历左右（再次找根节点）

  public TreeNode buildTree(int[] preorder, int[] inorder) { // 3,9,20,15,7(i)       9,3,15,20,7(j)
            TreeNode treeNode;
            //1.遍历preorder，看哪个在inorder中首先出现(首先出现就是当前的根节点)
            for (int i = 0; i < preorder.length; i++) {
                for (int j = 0; j < inorder.length; j++) {
                    if (preorder[i] == inorder[j]){  //3
                        //2.说明这个结点是根节点
                        treeNode = new TreeNode(preorder[i]);
                        //3.递归遍历找到当前结点的左右结点
                        int[] left = new int[j];  // 9
                        for (int k = 0; k < j; k++) {
                            left[k] = inorder[k];
                        }
                        treeNode.left = buildTree(preorder, left);
                        int[] right = new int[inorder.length - j - 1];  // 15 20 7
                        for (int k = 0; k < right.length; k++) {
                            right[k] = inorder[k + j + 1];
                        }
                        treeNode.right = buildTree(preorder, right);

                        //4.返回当前结点
                        return treeNode;
                    }
                }
            }

            return null;
        }