A level-order-traverse BFS queue based Java implementation


  • 0

    Not to say is a good way. Actually, this method takes more time to run and require O(N) extra space. This is to show how similar code is as the question 102. level-order-traverse tree The only change here to made is to make sure at each level, avoid using .next pointer to the last element by if(i == n - 1) continue;

    Here is my short Java implementation. And could also be an AC answer to 116. Populating Next Right Pointers in Each Node

        public void connect(TreeLinkNode root) {
            Queue<TreeLinkNode> q = new LinkedList<>();
            if (root == null) return;
            q.offer(root);
            while(!q.isEmpty()){
                int n = q.size();
                TreeLinkNode node = q.poll();
                for (int i = 0; i < n; i++){
                    if(node.left != null) q.add(node.left);
                    if(node.right != null) q.add(node.right);
                    if(i == n - 1) continue;
                    node.next = q.poll();
                    node = node.next;
                }
            }
        }
    

Log in to reply
 

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