Concise and clear solution!


  • 1
    S

    Tried to make it as clear as possible!

    class Solution {
        public int widthOfBinaryTree(TreeNode root) {
                    if (root == null) return 0;
            int maxwidth = 0;
            Queue<NodeIndex> queue = new LinkedList<>();
            queue.offer(new NodeIndex(root, 0));
    
            while (!queue.isEmpty()) {
                int size = queue.size();
                int start=0;
                int end=0;
                for (int i=0; i<size; i++) {
                    NodeIndex nodeIndex = queue.poll();
                    TreeNode node = nodeIndex.node;
                    int index = nodeIndex.index;
                    if (i==0) start = index;
                    if (i==size-1) end = index;
                    if (node.left!=null) queue.offer(new NodeIndex(node.left, index*2));
                    if (node.right!=null) queue.offer(new NodeIndex(node.right, index*2+1));
                }
                maxwidth = Math.max(maxwidth, end-start+1);
            }
            return maxwidth;
        }
        
        class NodeIndex {
            TreeNode node = null;
            int index = 0;
            public NodeIndex(TreeNode node, int index) {
                this.node = node;
                this.index = index;
            }
        }
    }
    
    

  • 0
    S

    Brilliant solution!! Thanks for sharing


Log in to reply
 

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