yet another Java recursive solution.


  • 0
    P

    The the main idea is to take the last element in postorder array as the root, find the position of the root in the inorder array; then locate the range for left sub-tree and right sub-tree and do recursion.

     public TreeNode buildTree(int[] inorder, int[] postorder) {
    		TreeNode root = helper (0, inorder.length - 1, postorder.length - 1, inorder, postorder);
    		return root;
    	}
    	
    	private TreeNode helper(int inStart, int inEnd, int postEnd, int[] inOrder, int[] postOrder){
    		if(inStart > inEnd || postEnd < 0)
    			return null;
    		
    		TreeNode node = new TreeNode(postOrder[postEnd]);
    		int index = 0;
    		for(int i = inStart;i <= inEnd; i++) {
    			if(inOrder[i] == postOrder[postEnd])  {
    				index = i;
                                    break;
                             }
    		}
    		int rightLen = inEnd - index; // Deep thinking. May be.
    		node.right = helper (index + 1, inEnd, postEnd - 1, inOrder, postOrder);
    		node.left = helper(inStart, index - 1, postEnd - rightLen - 1, inOrder, postOrder); // This part is challenging to understand for beginners.
    		
    		return node;
    	}
    

Log in to reply
 

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