AC JAVA Solution with Explanation


  • 0

    A property of Binary tree is that index of left child = index of parent2, index of right child = index of parent2 + 1.We could use this to get the width for each level.

    public int widthOfBinaryTree(TreeNode root) {
        if(root==null) return 0;
        if(root.left==null&&root.right==null) return 1;
        LinkedList<TreeNode> q1 = new LinkedList<>(); // keep track of node
        LinkedList<Integer> q2 = new LinkedList<>(); // queue that keep track of index of each node
        q1.offer(root);
        q2.offer(1);
        int size = 1;// keep track of current num of nodes in q1 for each level
        int max = Integer.MIN_VALUE;
        boolean fir = false;// judge whether its the first node in a new level
        int start = Integer.MAX_VALUE;// record index of first node in a new level
        while(!q1.isEmpty()){
            TreeNode node = q1.poll();
            int i = q2.poll();
            size--;
            if(fir){
                start = i;
                fir = false;
            }
            if(node.left!=null){
                q1.offer(node.left);
                q2.offer(i*2);
            }
            if(node.right!=null){
                q1.offer(node.right);
                q2.offer(i*2+1);
            }
            if(size==0){
                fir = true;
                size = q1.size();
                max = Math.max(max, i - start + 1);// the i is the index of last node in this level
            }
        }
        return max;
    }
    

Log in to reply
 

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