Share 6ms Java Solution


  • 0
    M
    public class Solution {
            public TreeNode buildTree(int[] preorder, int[] inorder) {
    		if (preorder == null || inorder == null) return null;
    		int m = preorder.length, n = preorder.length;
    		if (m != n || m == 0) return null;
    		Map<Integer, Integer> inds = new HashMap<Integer, Integer>();
    		for (int i = 0; i < n; ++i) inds.put(inorder[i], i);
    		return buildTree(preorder, inorder, 0, n - 1, 0, n - 1, inds);
    	}
    	
    	public TreeNode buildTree(int[] preorder, int[] inorder, int pLo, int pHi, int iLo, int iHi, Map<Integer, Integer> inds) {
    		if (pLo > pHi || iLo > iHi) return null;
    		int rootVal = preorder[pLo];
    		TreeNode root = new TreeNode(rootVal);
    		int inRootInd = inds.get(rootVal);
    		int leftLen = inRootInd - iLo;
    		root.left = buildTree(preorder, inorder, pLo + 1, pLo + leftLen, iLo, inRootInd - 1, inds);
    		root.right = buildTree(preorder, inorder, pLo + leftLen + 1, pHi, inRootInd + 1, iHi, inds);
    		return root;
    	}
    }
    

Log in to reply
 

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