Tree depth and width

Avg depth of tree

class TreeNode{
    int val;
    TreeNode left;
    TreeNode right;
    public TreeNode(int val){
        this.val = val;
    }
}

double avgDepth(TreeNode root){
    if(root == null) return 0.0;
    Queue<TreeNode> q = new LinkedList<>();
    int sum = 0;
    int count = 0;
    int depth = 0;
    q.add(root);

    while(!q.isEmpty()){
        depth++;
        int size = q.size();
        for(int i=0; i<size; i++){
            TreeNode cur = q.poll();
            if(cur.left==null && cur.right==null){
                count++;
                sum += depth;
            }
            if(cur.left != null){
                q.add(cur.left);
            }
            if(cur.right != null){
                q.add(cur.right);
            }
        }
    }
    return (double)sum/count;
}

662. Maximum Width of Binary Tree

Iterative

• 必須有個資料結構記住node index

• Record the first node index

• 找到level最後一個node的時候比較width

 def widthOfBinaryTree(self, root: TreeNode) -> int:
    res = 0
    left = 0
    q = []
    q.append((root, 1))
    
    while q:
        size = len(q)
        for i in range(size):
            node, idx = q.pop(0)
            if i == 0:
                left = idx
            if i == size-1:
                res = max(res, idx - left + 1)
            
            if node.left:
                q.append((node.left, idx*2))
            if node.right:
                q.append((node.right, idx*2+1))
    return res

dfs

• 用一個list儲存每個level的第一個idx, 每個node都比較一次

int ans = 0;
public int widthOfBinaryTree(TreeNode root){ 
    List<Integer> list = new ArrayList<>();
    helper(root, 0, 0, list);
    return ans;
}

private void helper(TreeNode node, int level, int idx, List<Integer> list){
    if(node == null) return;

    // 放入這個level的第一個idx
    if(level == list.size()){
        list.add(idx);
    }

    ans = Math.max(ans, idx - list.get(level) + 1);
    helper(node.left, level+1, 2*idx, list);
    helper(node.right, level+1, 2*idx+1, list);
}