simple Java code based on the classic queue-powered BFS


  • 0
    A
    class Solution {
    public int widthOfBinaryTree(TreeNode root) {
        // algorithm 2017/08/20: BFS tree traversal, but we want to record the horizontal position of each node in its level
        int result                  = 0;
        if (null == root) {
            return result;
        }
    
        Queue<TreeNodeAndPos> queue = new LinkedList<>();
        queue.offer(new TreeNodeAndPos(root, 0));
        
        while (!queue.isEmpty()) {
            int countNodesInLevel         = queue.size();
            int minPosInLevel             = 0;
            int maxPosInLevel             = 0;
            for (int index = 0; index < countNodesInLevel; index++) {
                TreeNodeAndPos treeNodeAndPos = queue.poll();
                TreeNode node                 = treeNodeAndPos.node;
                int posInLevel                = treeNodeAndPos.posInLevel;
                if (0 == index) {
                    minPosInLevel = posInLevel;
                }
                if (countNodesInLevel - 1 == index) {
                    maxPosInLevel = posInLevel;
                }
                
                // enqueue
                if (null != node.left) {
                    queue.offer(new TreeNodeAndPos(node.left, 2*posInLevel));
                }
                if (null != node.right) {
                    queue.offer(new TreeNodeAndPos(node.right, 2*posInLevel+1));
                }
            }
            result = Math.max(result, maxPosInLevel - minPosInLevel + 1);
        }
        
        return result;   
    }
    
    class TreeNodeAndPos {
        public TreeNodeAndPos(TreeNode node, int posInLevel) {
            this.node       = node;
            this.posInLevel = posInLevel;
        }
        TreeNode node;
        int posInLevel;
    }
    

    }


Log in to reply
 

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