LeetCode_65_ConstructBinaryTreeFromPreorderAndInorderTraversal

1. question: 从前序与中序遍历序列构造二叉树（中等）

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal

示例 1:

输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]

示例 2:

输入: preorder = [-1], inorder = [-1]
输出: [-1]

提示:

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

2. answers

这道题和前一道题类似，只不过把后序序列变成了前序序列。

此时，前序的首元素就是当前的根节点。前序左子序列从第二个元素开始。思路上一道题类似，代码如下：

public class Solution_0064 {

    public static TreeNode recurTree(int[] preorder, int preLeft, int preRight, int[] inorder, int inLeft, int inRight) {

        // 注意递归结束条件
        
        // 递归未结束，找到当前根节点
        TreeNode root = new TreeNode(preorder[preLeft]);

        // 从中序序列中找到跟节点
        int rootIndex = 0;

        for (int i = inLeft; i < inRight + 1; i++) {

            if(inorder[i] == root.val) {
                rootIndex = i;
                break;
            }
        }

        // 根据划分的中序子序列 划分 对应的前序子序列
        // 定义 preIndex为前序左子序列的最后一个元素下标
        // 计算子序列长度
        int preIndex = rootIndex - 1 - inLeft + 1;
        preIndex = preLeft + 1 + preIndex - 1;


        // 判断是否有左子树
        if(rootIndex == inLeft) root.left = null;
        else root.left = recurTree(preorder, preLeft + 1, preIndex, inorder, inLeft, rootIndex - 1);

        // 判断是否有右子树
        if(rootIndex == inRight) root.right = null;
        else root.right = recurTree(preorder, preIndex + 1, preRight, inorder, rootIndex + 1, inRight);

        return root;
    }

    public static TreeNode buildTree(int[] preorder, int[] inorder) {

        return recurTree(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
    }

    public static void main(String[] args) {
        System.out.println();

        int[] inorder = {9, 3, 15, 20, 7};
        int[] pretorder = {3, 9, 20, 15, 7};

//        int[] inorder = {-1};
//        int[] postorder = {-1};

        TreeNode root = buildTree(pretorder, inorder);

        TreeNode root = buildTree(pretorder, inorder);

        // 遍历输出
        Queue<TreeNode> queue = new LinkedList<>();

        queue.offer(root);

        while(queue.size() > 0) {
            int length = queue.size();

            while(length-- > 0) {

                root = queue.poll();
                System.out.print(root.val + "\t");

                if(root.left != null) queue.offer(root.left);
                if(root.right != null) queue.offer(root.right);
            }
        }
    }
}

3. 备注

参考力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com)，代码随想录 (programmercarl.com)。