二叉树-构造二叉树

• • 前序+中序构造二叉树
  • 前序+后序构造二叉树
  • 前序遍历构造二叉搜索树

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

class Solution {
    Listam=new ArrayList<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return dfs(preorder,0,preorder.length-1,inorder,0,inorder.length-1);

    }

    private TreeNode dfs(int[] preorder, int pL, int pR, int[] inorder, int iL, int iR) {
        if(pL>pR) return null;

        TreeNode root=new TreeNode(preorder[pL]);
//        am.add(preorder[pL]);如果是求后序遍历的序列，就在这里记录即可，万变不离其宗

        //在中序遍历中找到根节点的位置
        int idx=0;
        while (inorder[idx]!=preorder[pL]){
            idx++;
        }
        int pLen=idx-iL;

        root.left=dfs(preorder,pL+1,pL+pLen,inorder,iL,idx-1);
        root.right=dfs(preorder,pL+pLen+1,pR,inorder,idx+1,iR);
        return root;
    }

}

添加链接描述
没有中序也是可以构造的

举例：
前序遍历为 [1] + [2, 4, 5] + [3, 6, 7]，
后序遍历为 [4, 5, 2] + [6, 7, 3] + [1].

找左分支的头节点，上栗中就是2，在前序中的下标preLeft+1，如果令左分支有 L 个节点的话。在后序中的下标则为L-1。

class Solution {
    public TreeNode constructFromPrePost(int[] pre, int[] post) {
        return build(pre,post,0,pre.length-1,0,post.length-1);
    }

    private TreeNode build(int[] pre, int[] post, int pl, int pr, int ql, int qr) {
        if(pl>pr){
            return null;
        }
        TreeNode node=new TreeNode(pre[pl]);
        if(pl==pr){ //不能掉
            return node;
        }
        //计算leftLen
        int p=ql;
        while (post[p]!=pre[pl+1]) {
            p++;
        }
        int leftLen=p-ql+1;
        node.left=build(pre,post,pl+1,pl+leftLen,ql,ql+leftLen-1);
        node.right=build(pre,post,pl+leftLen+1,pr,ql+leftLen,qr-1);
        return node;
    }
}

添加链接描述
对preorder排序得到中序遍历，前+中=》bst