Java easy understanding solution based on BSF level order traverse


  • 0
    N

    Based on the BSF level order travser. Use another Queue to store temporary data for each level.
    Use a list to connect next node
    for (int i = 0; i < list.size() - 1; i++){
    list.get(i).next = list.get(i+1);
    }

    public class Solution {
        public void connect(TreeLinkNode root) {
            if (root == null || (root.left == null && root.right == null)){
                return;
            }
            
            Queue<TreeLinkNode> q = new LinkedList<>();
            
            q.offer(root);
            while (!q.isEmpty()){
                Queue<TreeLinkNode> qq = new LinkedList<>();
                List<TreeLinkNode> list = new ArrayList<>();
                int size = q.size();
                for (int i = 0; i < size; i++){
                    TreeLinkNode temp = q.poll();
                     list.add(temp);
                    if (temp.left != null){
                        qq.offer(temp.left);
                    }
                    if (temp.right != null){
                        qq.offer(temp.right);
                    }
                }
                for (int i = 0; i < list.size() - 1; i++){
                    list.get(i).next = list.get(i+1);
                }
                q = qq;
            }
            
        }
    }
    

  • 0

Log in to reply
 

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