Populating Next Right Pointers in Each Node II solution with comments


  • 0
    J
    /**
     * 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) {
            if(root==null)
                return;
            root.next=null;
            setpoint(root);
            
        }
        void setpoint(TreeLinkNode node)
        {
            TreeLinkNode t=node;
            //return if node is null or node has no children
            if(node==null || (node.right==null && node.left==null))
            {
                return;
            }
            //right node is null
            if(t.right==null)
            {
                //traverse linked-list of parent to find first node with at least one children
                t=t.next;
                while(t!=null && (t.right==null && t.left==null)  )
                {
                t=t.next;
                }
                //set link for left node
                if(t==null)
                {
                    node.left.next=null;
                }
                else
                {
                     if(t.left!=null)
                        node.left.next=t.left;
                    else
                        node.left.next=t.right;
                }
               
                setpoint(node.left);
               
            }
            else
            {
                //set link for left node
                if(node.left!=null)
                {
                    node.left.next=node.right;
                        
                }
                //traverse linked-list of parent to find first node with at least one children   
                t=t.next;
                 while( t!=null && ( t.right==null && t.left==null)  )
                {
                t=t.next;
                 
                }
                
                //set link for right node 
                if(t==null )
                {
                    node.right.next=null;
                }
                else
                {
                     if(t.left!=null)
                        node.right.next=t.left;
                    else
                        node.right.next=t.right;
                }
                //recursively solve for right subtree
                setpoint(node.right);
                ////recursively solve for left subtree
                setpoint(node.left);
            }
        }
    }
    

Log in to reply
 

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