Share my easy Java Solution with recursive


  • 0
    A

    It's similar to Construct Binary Tree from Preorder and Inorder Traversal.
    The only difference is that we find the root from the tail of postorder[]

    
    class Solution {
        public TreeNode buildTree(int[] inorder, int[] postorder) {
            return builder(postorder.length-1,0,inorder.length-1,inorder,postorder);
        }
        public TreeNode builder(int postIndex,int inStart, int inEnd, int[]inorder,int[]postorder){
            if(inStart>inEnd)
                return null;
            TreeNode root = new TreeNode(postorder[postIndex]);
            //find index of root in inorder[]
            int index=0;
            for(int i =0;i<postorder.length;i++){
                if(inorder[i]==postorder[postIndex])
                    index = i;
            }
            //                   postIndext                 inStart  inEnd    int[]   int[]
            root.right = builder(postIndex-1              , index+1, inEnd   ,inorder,postorder);
            root.left  = builder(postIndex-1-(inEnd-index), inStart, index-1 ,inorder,postorder);
            return root;
        }
    
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.