【力扣】105. 从前序与中序遍历序列构造二叉树

【力扣】105. 从前序与中序遍历序列构造二叉树

题目：
给定一棵树的前序遍历 preorder 与中序遍历 inorder。请构造二叉树并返回其根节点。

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

提示:

1 <= preorder.length <= 3000
inorder.length == preorder.length
-3000 <= preorder[i], inorder[i] <= 3000
preorder 和 inorder 均无重复元素
inorder 均出现在 preorder
preorder 保证为二叉树的前序遍历序列
inorder 保证为二叉树的中序遍历序列

答案：

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTreeByPreAndIn(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
    }
    public TreeNode buildTreeByPreAndIn(int[] pre, int startPre, int endPre, int[] in, int startIn, int endIn){
         if(startPre > endPre || startIn > endIn){
            return null;
        }
        TreeNode root  = new TreeNode(pre[startPre]);
        for(int i = startIn; i <= endIn; i++){
            if(in[i] == pre[startPre]){
                root.left = buildTreeByPreAndIn(pre, startPre+1, startPre + (i - startIn), in, startIn, i-1); //左孩子是中序遍历根节点左子树的根节点
                root.right = buildTreeByPreAndIn(pre, startPre + (i-startIn) + 1, endPre, in, i+1, endIn);//右孩子是中序遍历根节点右子树的根节点
            }
        }
        return root;
    }
}