1ms Easy java solution


  • 0
    D
    /**
     * Definition for binary tree with next pointer.
     * public class TreeLinkNode {
     *     int val;
     *     TreeLinkNode left, right, next;
     *     TreeLinkNode(int x) { val = x; }
     * }
     */
    public class Solution {
        public void connect(TreeLinkNode root) {
            
            //Base case: if root is null, return
            if(root==null)
                return;
                
            //update next of root to null
            root.next=null;
            
            //call function to connect right pointers
            connectNext(root);
        
        }
        
        public void connectNext(TreeLinkNode root)
        {
            // Base case: if root is null, return
            if(root==null)
                return;
                
            //General case: if node is present
            
            //update left subtree next pointer
            if(root.left!=null)
            {
                //if sibling is present
                if(root.right!=null)
                    root.left.next=root.right;
                
                //to connect to parents siblings nodes
                else
                {
                boolean flag=false;
                
                TreeLinkNode current=root;
    
            //iterate until you find a node with a child to connect next pointer
                while(current.next!=null)
                {
                    current=current.next;
                    
                    if(current.left!=null)
                    {
                        root.left.next=current.left;
                        flag=true;
                        break;
                        
                    }
                    else if(current.right!=null)
                    {
                        root.left.next=current.right;
                        flag=true;
                        break;
                        
                    }
                }
                
              //if no such node present, connect it to null
                if(!flag && current.next==null)
                    root.left.next=null;
              }
            }
            
            if(root.right!=null)
            {
                //to connect to parents siblings nodes
                boolean flag=false;
                TreeLinkNode current=root;
    
             //iterate through the nodes until you find a child node
                while(current.next!=null)
                {
                    current=current.next;
                    
                    if(current.left!=null)
                    {
                        root.right.next=current.left;
                        flag=true;
                        break;
                        
                    }
                    else if(current.right!=null)
                    {
                        root.right.next=current.right;
                        flag=true;
                        break;
                        
                    }
                    
                    
                        
                }
                
              //if no node found, return null
                if(!flag && current.next==null)
                    root.right.next=null;
            }
            
            //call function recursively on right and left subtrees , IN THIS ORDER!!
            connectNext(root.right);
            
            connectNext(root.left);
                
            
        }
    }
    

  • 0
    S

    Can you explain why "right" first, and then "left"?

    Thanks.


  • 1
    D

    Hi @serious ,

    The reason is that you want the next pointers of the nodes in ALL levels before the one you are currently on, to be updated.

    If you do it with recursing first on the left and then on the right, the next pointer of each node in previous levels, will not be updated.

    You can try it and take a look.

    Hope this answers your question.

    Thanks.
    Deepak.


Log in to reply
 

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