[662. Maximum Width of Binary Tree] #leetcode

662_0901.java

class Solution {
  // O(n) O(n)
    public int widthOfBinaryTree(TreeNode root) {
        if ( root == null ) return 0;
        
        Deque<TreeNode> queue = new LinkedList<TreeNode>();
        List<Integer> idx = new ArrayList<Integer>();
        
        queue.addLast(root);
        idx.add(0);
        
        int res = 1;
        while (!queue.isEmpty()) {
            res = Math.max(res, idx.get(idx.size()-1) - idx.get(0) + 1);
                
            List<Integer> levelIdx = new ArrayList<Integer>();
            int n = queue.size();
            for (int i = 0; i < n ; i++ ) {
                TreeNode node = queue.removeFirst();
                if (node.left != null) {
                    queue.addLast(node.left);
                    levelIdx.add(idx.get(i) * 2);
                }
                if (node.right != null) {
                    queue.addLast(node.right);
                    levelIdx.add(idx.get(i) * 2 + 1);
                }
            }
            idx = levelIdx;
        }
        return res;
    }
}

class Solution {
  // O(n) O(h)
    public int widthOfBinaryTree(TreeNode root) {
        List<Integer> leftMost = new ArrayList<Integer>();
        return dfs(root, 1, 0, leftMost);
    }
    
    private int dfs(TreeNode node, Integer idx, Integer depth, List<Integer> leftMost) {
        if (node == null) return 0;
        if (depth >= leftMost.size()) leftMost.add(idx);
        int cur = idx - leftMost.get(depth) + 1;
        int left = dfs(node.left, idx * 2, depth+1, leftMost);
        int right = dfs(node.right, idx*2+1, depth+1, leftMost);
        return Math.max(cur, Math.max(left, right));
    }
    
}