[4.4] Create a linked list of all nodes at each depth

1. Example

Level=> level order traversal => Breath First Search

 Method1: list = new LinkedList(); 

 Method2: TreeLinkNode head = root; // use TreeLinkNode next feature as a queue

if ( curHead == null )
{
curHead= lastCur.left;
pre = curHead; }
else
{
pre.next = lastCur.left or ritght
}
// NOTE : the reason need two layer of while is because we no idea 
when to update lastHead even we have curHead complete
while (lastHead != null) { 

      TreeLinkNode lastCur = lastHead; // Like while (!queue.isEmpty()) 

      while ( lastCur != null ) // like for loop in the above {

                         

            lastCur = lastCur.next;  

  

       }  

       lastHead = curHead;  

       curHead = null;

}

OR

    //while(lastHead!=null)  

    //{  

       // TreeLinkNode lastCur = lastHead;  

        while(lastCur != null)  

        { 

            .....

            if (lastCur == null)

            {

                  lastCur = curHead;  

                  curHead = null;

            }

         1
       /  \
      2    3
     / \  / \
    4  5  6  7

After calling your function, the tree should look like:

         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \  / \
    4->5->6->7 -> NULL

NOTE: At leaves, for loop all leaves but doesn't add any nodes
list = new LinkedList(); 

 for ( int i = 0 ; i < result.get(level).size();i++ ) { // Like a queue in-insertion order

    TreeNode n = (TreeNode) result.get(level).get(i);

    if ( n ! = null ) {
               if (n.left != null) 

                    list.add(n.left); 

               if (n.right != null) 

                     list.add(n.right);

    }
   if (list.size() > 0 ) { 

           result.add(level+1, list); 

    } 

     else { 

     break; 

     } 

     level++;



2. Implementation
In a usual BST, we simply traverse the nodes without caring which level we are on. In this case, it is critical to know the level.
We thus use a dummy node to indicate when we have finished one level and are starting on the next.

public List> findLevelLinkedList(  TreeNode root ) 
{


       int level = 0;
       List> res = new ArrayList>();
       LinkedList list = new LinkedList();
       queue.add(root);
       res.add(level, list);


       
       while(true)
       {



             // NOTE: a new linked list start with a new level
             list = new LinkedList();
             for ( int i = 0 ; i < result.get(level).size();i++ )
             {
                  TreeNode cur = (TreeNode) result.get(level).get(i);
                  if ( cur ! = null )
                  {
                        if (cur.left != null)
                           list.add(cur.left);
                        if (cur.right != null)
                           list.add(cur.right);
                  }
             }



             if (list.size() > 0 )
             {
                   result.add(level+1, list);
             } 
             else
             {
                   break;
             }



             level++;




       }
 

   

       return result;
 


}

struct TreeLinkNode {
      TreeLinkNode *left;
      TreeLinkNode *right;
      TreeLinkNode *next;
}    
public void findLevelLinkedList (TreeNode root)
{



      // vlaidate hte input
      if (root == null)
          return;


      
      TreeLinkNode lastHead = root;   // As a queue
      TreeLinkNode pre = null;
      TreeLinkNode curHead = null;
      //int lastNum = 1;
      //int curNum = 0;
        


      while (lastHead != null)
      {
           TreeLinkNode lastCur = lastHead;
           // Like while (!queue.isEmpty())
           while ( lastCur != null ) // like for loop in the baove
           {
                  if (lastCur.left != null)
                  {
                       if (  curHead == null )
                       {
                             curHead= lastCur.left;
                             pre = curHead;
                       }
                       else 
                       {
                             pre.next = lastCur.left;
                             pre = pre.next;
                       }
                  }
                  if (lastCur.right != null ) 
                  {
                       if (   curHead == null )
                       {
                              curHead = lastCur.right;
                              pre = curHEad;
                       }
                       else 
                       { 
                              pre.next = lastCur.next;
                              pre = pre.next;
                       }
                  }


                  lastCur = lastCur.next;// next element in Queue
                  
           }


           lastHEad = curHead; // new linkedl list in current level
           curHead = null;

      }
       
}

3. similar Ones