BFS with Indexed TreeNode Wrapper and Queue & Stack


  • 0
    X

    Using a wrapper TreeNode class to store the index of each TreeNode at specified level, using a queue to store the first element of specified level, and using a stack to store the last element of that level, then the difference would be the width of that specific level, we compare it with the previous max and update the max when necessary.

    /**My BFS Solution with Indexed Wrapper TreeNode class**/
        class IndexedNode {
            TreeNode left;
            TreeNode right;
            int val;
            int index;      //index of TreeNode at specified level
            IndexedNode(TreeNode node, int index) {
                this.left = node.left;
                this.right = node.right;
                this.val = node.val;
                this.index = index;
            }
        }
    
        public int widthOfBinaryTree(TreeNode root) {
            if (root == null) return 0;
            int missingTotal = 0;
            int maxWidth = 1;
            Queue<IndexedNode> q = new LinkedList();
            q.offer(new IndexedNode(root, 0));
            
            while (!q.isEmpty()) {
                int size = q.size();
                Stack<IndexedNode> s = new Stack();
                
                for (int i = 0; i < size; i++) {
                    IndexedNode temp = q.poll();
                    if (temp.left != null) {
                        IndexedNode left = new IndexedNode(temp.left, temp.index * 2);
                        q.offer(left);
                        s.push(left);
                    } 
    
                    if (temp.right != null) {
                        IndexedNode right = new IndexedNode(temp.right, temp.index * 2 + 1);
                        q.offer(right);
                        s.push(right);
                    } 
                }
    
                if (!s.isEmpty()) {
                    maxWidth = Math.max(maxWidth, s.peek().index - q.peek().index + 1);    
                }
            }
    
            return maxWidth;
        }
    

Log in to reply
 

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