秋招力扣刷题——从前序与中序遍历序列构造二叉树

一、题目要求

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

二、解法思路

• 根据二叉树的遍历结构重构二叉树，至少两种遍历方式结合，且其中一种必须是中序遍历。
• 思路：根据前序遍历找到根节点，然后从中序遍历中找到根节点的下标，拆分数组分别构造左子树和右子树。
• 代码1：此代码分割数组是左闭右开

class Solution {
    Map<Integer,Integer> cache=new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        for(int i=0;i<inorder.length;i++){
            cache.put(inorder[i],i);
        }
        return build(preorder,0,preorder.length,inorder,0,inorder.length);
    }
    private TreeNode build(int[] preorder,int prestart,int preend,int[] inorder,int instart,int inend){
            if(prestart>=preend||instart>=inend)return null;
            TreeNode root=new TreeNode(preorder[prestart]);
            int leftnum=cache.get(preorder[prestart])-instart;
            //前序加1是因为要跳过根节点
            root.left=build(preorder,prestart+1,prestart+leftnum+1,inorder,instart,instart+leftnum);
            //中序加一也是因为要跳过根节点
            root.right=build(preorder,prestart+leftnum+1,preend,inorder,instart+leftnum+1,inend);
            return root;
        }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

• 代码2：次代码分割数组是左闭右闭

class Solution {
    Map<Integer,Integer> cache=new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(inorder.length==1)return new TreeNode(inorder[0]);
        for(int i=0;i<inorder.length;i++){
            cache.put(inorder[i],i);
        }
        return build(preorder,inorder,0,preorder.length-1,0,inorder.length-1);
    }
    private TreeNode build(int[] preorder,int[] inorder,int prebegin,int preend,int inbeggin,int inend){
        if(prebegin>preend||inbeggin>inend)return null;
        TreeNode root=new TreeNode(preorder[prebegin]);
        int index=cache.get(preorder[prebegin]);
        int leftnum=index-inbeggin;
        root.left=build(preorder,inorder,prebegin+1,prebegin+leftnum,inbeggin,inbeggin+leftnum);
        root.right=build(preorder,inorder,prebegin+leftnum+1,preend,inbeggin+leftnum+1,inend);
        return root;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

注：两种代码的结束条件以及分割的右区间处理方式不同，后者更容易理解一点。