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 保证为二叉树的中序遍历序列

思路

前序遍历数组中的第一个元素是当前二叉树的根节点。获取根节点在中序数组中的位置可以知道左右两棵子树的元素，从而可以知道在前序数组中两棵子树的位置。此时左右子树又可以分别看成单独的两棵树，从而可以利用递归重复上述过程。递归的终止条件就是当前节点为叶子节点或者为null。

解法

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length == 0) {
            return null;
        }
        return build(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
    }

    public TreeNode build(int[] preorder, int preLeft, int preRight, int[] inorder, int inLeft, int inRight) {
        if (preLeft > preRight) {
            return null;
        }
        if (preLeft == preRight) {
            return new TreeNode(preorder[preLeft]);
        }

        TreeNode root = new TreeNode(preorder[preLeft]);
        //获取根节点在中序数组中的位置
        int inorderSeparatorPos = findInorderSeparatorPos(inorder, root.val);
        //根据中序数组中根节点的位置从而可以知道左右子树节点数量，从而可以知道两者在前序子数组中的分隔位置。
        int preorderSeparatorPos = inorderSeparatorPos - inLeft + preLeft;
        
        //递归求左子节点
        root.left = build(preorder, preLeft + 1, preorderSeparatorPos, inorder, inLeft, inorderSeparatorPos - 1);
        //递归求右子节点
        root.right = build(preorder, preorderSeparatorPos + 1, preRight, inorder, inorderSeparatorPos + 1, inRight);
        
        return root;
    }

    /**
     * 获取根节点在中序数组中的位置
     */
    public int findInorderSeparatorPos(int[] inorder, int val) {
        for (int i = 0; i < inorder.length; i++) {
            if (inorder[i] == val) {
                return i;
            }
        }
        return -1;
    }
}