题目描述

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

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

示例 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

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

解题思路

题目要求通过前序遍历和中序遍历生成二叉树
前序遍历：先输出根节点，然后再输出左子树和右子树
中序遍历：先输出左子树，然后输出根节点，最后输出右子树
通过观察发现：
1、前序遍历数组的第一个节点是根节点
2、在中序遍历数组中，根节点所在位置左侧的节点属于左子树，右侧节点属于右子树
使用递归实现，找到根节点，然后将剩余节点分为左子树和右子树，不断寻找根节点，拆分剩余节点，直至只有一个节点或没有节点

代码

class Solution {
        public TreeNode buildTree(int[] preorder, int[] inorder) {
          return buildRoot(preorder,0,preorder.length-1,inorder,0,inorder.length-1);
        }
        public TreeNode buildRoot(int[] preorder,int preStart,int preEnd,int[] inorder,int inStart,int inEnd){
            int length = preEnd-preStart;
            if(length<0)return null;
            TreeNode root = new TreeNode(preorder[preStart]);
            if(length==0)return root;
            int pos = 0;
            while(inStart+pos<inEnd){
                if(inorder[inStart+pos]==root.val){
                    break;
                }
                pos++;
            }
            if(pos > 0){

                root.left=buildRoot(preorder,preStart+1,preStart+pos,inorder,inStart,inStart+pos-1);
            }
            if(inStart + pos < inEnd){

                root.right=buildRoot(preorder,preStart+pos+1,preEnd,inorder,inStart+pos+1,inEnd);
            }
            return root;
        }
    }