Java Preorder O(n) Time O(h) Space


  • 0
    public int widthOfBinaryTree(TreeNode root) {
        Map<Integer, Integer[]> map = new HashMap<>();
        preorder(root, 0, 1, map);
        int maxWidth = 0;
        for (Integer[] diff : map.values()) maxWidth = Math.max(maxWidth, diff[1] - diff[0] + 1);
        return maxWidth;
    }
    
    public void preorder(TreeNode root, int row, int pos, Map<Integer, Integer[]> map) {
        if (root == null) return;
        Integer[] cur = map.getOrDefault(row, new Integer[2]);
        if (cur[0] == null || pos < cur[0]) cur[0] = pos;
        if (cur[1] == null || pos > cur[1]) cur[1] = pos;
        map.put(row, cur);
        preorder(root.left, row+1, 2*pos - 1, map);
        preorder(root.right, row+1, 2*pos, map);
    }
    

Log in to reply
 

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