Java straightforward method that surprisingly fast, 2ms


  • 0
    H

    Here is my thought. Suppose a node is X, and its left child is Y ( Y can be a node or a traversal of a tree ).
    In postorder traversal it is ...Y.....X...
    In inorder traversal it is ...YX.......
    The ..... in between presents a tree which root is the right child of X. I take out this part and call the function again to construct the right side treee.

    It is clearly not optimistic but it is fast. Also in my method recursive only happens for constructing rightside tree.

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        int i=0;
        int j=0;
        TreeNode root=null;
        while (i<inorder.length && j<postorder.length) {
        	if (inorder[i]==postorder[j]) {
        		TreeNode node = new TreeNode(inorder[i]);
        		node.left=root;
        		root = node;
        		i++;
        		j++;
        	} else {
        		TreeNode node = new TreeNode(inorder[i]);
        		node.left=root;
        		root = node;
        		int k=j;
        		while (postorder[k]!=inorder[i]) {
        			k++;
        		}
        		int[] ia = Arrays.copyOfRange(inorder, i+1, i+1+k-j);
        		int[] pa = Arrays.copyOfRange(postorder, j, k);
        		node = buildTree(ia, pa);
        		root.right=node;
        		i=k+1;
        		j=k+1;
        	}
        }
        return root;
    }

Log in to reply
 

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