LC106. 从中序与后序遍历序列构造二叉树

2023-12-31 17:35:13

参考:代码随想录?


class Solution {
    Map<Integer,Integer> map ;

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        map = new HashMap<>();
        for(int i= 0 ; i < inorder.length; i ++){
            map.put(inorder[i],i);
        }

        return findNode(inorder,0,inorder.length-1,
                        postorder,0,postorder.length-1);
    }


    public TreeNode findNode(
            int[] inorder, int inBegin, int inEnd, 
            int[] postorder, int postBegin, int postEnd)
    {
            // 左闭右闭的写法
            if(inBegin > inEnd || postBegin > postEnd){
                return null;
            }

            int rootIndex = map.get(postorder[postEnd]);
            TreeNode root = new TreeNode(inorder[rootIndex]);


            int lenOfLeft = rootIndex - inBegin;

            root.left = findNode(inorder,inBegin,rootIndex-1,
                    postorder,postBegin,postBegin+lenOfLeft-1);

            root.right = findNode(inorder,rootIndex+1,inEnd,
                    postorder,postBegin+lenOfLeft,postEnd-1);
            return root;
    }
}

文章来源:https://blog.csdn.net/xuan__xia/article/details/135317321
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。