Java solution using HashMap for faster searches for node val in inorder


  • 0
    public class Solution {
        public TreeNode buildTree(int[] preorder, int[] inorder) {
            if(preorder.length ==  0 || inorder.length == 0) {
                return null;
            }
            
            Map<Integer, Integer> subtreeMap = new HashMap<>();
            for(int i = 0; i < inorder.length; i++) {
                subtreeMap.put(inorder[i], i);
            }
            
            return buildTree(preorder, inorder, 0, subtreeMap, 0, inorder.length - 1);
        }
        
        private TreeNode buildTree(int[] preorder, int[] inorder, int preStart,
            Map<Integer, Integer> subtreeMap, int inStart, int inEnd) {
            if(inStart == inEnd) {
                int nextRootIndex = inStart;
                TreeNode nextRoot = new TreeNode(inorder[nextRootIndex]);
               
                return nextRoot;
            }
            
            Integer nextRootIndex = subtreeMap.get(preorder[preStart]);
            TreeNode nextRoot = new TreeNode(inorder[nextRootIndex]);
            if(nextRootIndex > inStart) {
                nextRoot.left = buildTree(preorder, inorder, preStart + 1, subtreeMap, inStart, nextRootIndex - 1);    
            }
            if(nextRootIndex < inEnd) {
                nextRoot.right = buildTree(preorder, inorder, preStart + nextRootIndex - inStart + 1, subtreeMap, nextRootIndex + 1, inEnd);
            }
            
           
            return nextRoot;
        }
    }
    

Log in to reply
 

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