Java O(n) simple code. follow up: what if duplicate items exist?


  • 0

    root in preorder is always the 1st item and we want to find the separation between left and right substree of preorder. We use hashmap to locate root position pos in inorder array to get it in O(1).
    Every node is constructed in O(1) time and the total nodes are n. so O(n) for both time and space complexity. Now I leave you guys a challenging follow up question: what if there are duplicate items.

    public class Solution {
        public TreeNode buildTree(int[] preorder, int[] inorder) {
            if (preorder == null || preorder.length == 0)
                return null;
            Map<Integer, Integer> map = new HashMap<>();
            int n = inorder.length;
            for (int i = 0; i < n; i++) {
                map.put(inorder[i], i);
            }
            return buildTree(preorder, inorder, map, 0, n - 1, 0, n - 1);
        }
        
        private TreeNode buildTree(int[] preorder, int[] inorder, Map<Integer, Integer> map, int p1, int p2, int i1, int i2) {
            if (p1 > p2)
                return null;
            TreeNode root = new TreeNode(preorder[p1]);
            int pos = map.get(preorder[p1]);
            root.left = buildTree(preorder, inorder, map, p1 + 1, pos - i1 + p1, i1, pos - 1);
            root.right = buildTree(preorder, inorder, map, pos - i1 + p1 + 1, p2, pos + 1, i2);
            return root;
        }
    }

Log in to reply
 

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