从前序遍历与中序遍历序列构造二叉树-蒲公英云

从前序遍历与中序遍历序列构造二叉树

桃扇骨 2023-09-30 09:47 125阅读 0赞

我们可以知道中序遍历时先遍历完左子树再遍历根结点最后遍历右子树，前序遍历是先遍历根结点再遍历左子树，最后遍历右子树，综上可知，前序遍历的(根+左子树)个数 = 中序遍历的(左子树+根)个数。利用这个性质，可知下边的:

对于前序遍历（根左右）

设前序遍历出的数组开始下标为preLeft，结束为preRight

根	左子树	右子树
preLeft	[preLeft+1,pIndex-inLeft+preLeft]	[pIndex-inLeft+preLeft+1,preRight]

对于中序遍历（左根右）

设中序遍历出数组开始下标为inLeft,结束下标为inRight

左子树	根	右子树
[inLeft-pIndex-1]	pIndex	[pIndex+1,inRight]

代码：

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int preLen = preorder.length;
        int vinLen = inorder.length;
        if(preLen!=vinLen) return null;
        Map<Integer,Integer> map = new HashMap<>();
        for(int i=0;i<vinLen;i++){
            map.put(inorder[i],i);
        }
        return buildTree(map,preorder,inorder,0,preLen-1,0,vinLen-1);
    }
    public TreeNode buildTree(Map<Integer,Integer> map,int[] preorder,int[] inorder,int preLeft,int preRight,int vinLeft,int vinRight){
        if(preLeft>preRight || vinLeft>vinRight) return null;
        int rootVal = preorder[preLeft];
        int pIndex =  map.get(rootVal);
        TreeNode root = new TreeNode(rootVal);
        root.left = buildTree(map,preorder,inorder,preLeft+1,pIndex-vinLeft+preLeft,vinLeft,pIndex-1);
        root.right = buildTree(map,preorder,inorder,pIndex-vinLeft+preLeft+1,preRight,pIndex+1,vinRight);
        return root;
    }
}