Java Solution 0 ms / Constant Space / Beats 74%/ Using 2 Pointers


  • 0
    M

    Idea: Iterate level by level. Start with level 1 (root.left & root.right). connect all the children in level2 (connect :: populate next pointers of the children) while processing nodes in the level1. repeat the process till no new level exist (as in no children exists of the first most node).

    public void connect(TreeLinkNode root) {
        if(root == null || root.left == null && root.right == null) return; // if only root or no root
        TreeLinkNode l = root.left;
        TreeLinkNode r = root.right;
        l.next = r; 
        TreeLinkNode start;
        while(l != null && r != null){ // this while is for going down the tree level by level
            start = l; // stores the first left pointer
    // this is for traversing with in a level as well as connecting the  child pointers for this level.
            while(l!= null && r!= null && l.left!=null){
                l.left.next = l.right;
                r.left.next = r.right;
                l.right.next = r.left;
                l = r;
                r = l.next;
            } 
    // increment the level by making the l & r pointers to start (first node in the level)'s children
            l = start.left;
            r = start.right;
        }
    }
    

Log in to reply
 

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