My O(n) Java solution with recursion and Map


  • 0
    L
    public class Solution {
        public TreeNode buildTree(int[] preorder, int[] inorder) {
            // write your code here
            if (preorder.length == 0 || inorder.length == 0) {
                return null;
            }
    
            Map<Integer, Integer> orderMap = new HashMap<Integer, Integer>();
            for (int i = 0; i < inorder.length; i++) {
                orderMap.put(inorder[i], i);
            }
    
            return buildTree(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1, orderMap);
        }
    
        private TreeNode buildTree(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd, Map<Integer, Integer> orderMap) {
            int rootVal = preorder[preStart];
            TreeNode root = new TreeNode(rootVal);
            if (preStart == preEnd) {
                return root;
            }
    
            int rootIndx = orderMap.get(rootVal);
    
            int leftNodesCount = rootIndx - inStart;
            int rightNodesCount = inEnd - rootIndx;
    
            if (leftNodesCount > 0) {
                root.left = buildTree(preorder, preStart + 1, preStart + leftNodesCount,
                        inorder, inStart, inStart + leftNodesCount - 1, orderMap);
            }
    
            if (rightNodesCount > 0) {
                root.right = buildTree(preorder, preStart + leftNodesCount + 1, preEnd,
                        inorder, inStart + leftNodesCount + 1, inEnd, orderMap);
            }
    
            return root;
        }
    }
    

Log in to reply
 

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