Java Simple O(1) space recursive solution


  • 0
    Z

    Hi there! I am sharing my solution, because I couldn't find any recursive solution implemented the same way with comments.

    public class Solution {
        public void connect(TreeLinkNode root) {
            if(root == null) return; // if node is null just return
            if(root.left != null){ // if left is not null then make left point to the right child
                root.left.next = root.right;
            }
            TreeLinkNode next = root.next; 
            while(next != null && next.left == null && next.right == null){ //find proper next node with at least one child
                next = next.next;
            }
            if(next != null){ // if proper next node, start assigning next pointers to childs
                if(root.right != null){ // if right child is not null then assign next pointer to it
                    if(next.left != null){
                        root.right.next = next.left;
                    } else {
                        root.right.next = next.right;
                    }
                } else if(root.left != null){ // if right is null then assign next pointer to the left child
                    if(next.left != null){
                        root.left.next = next.left;
                    } else {
                        root.left.next = next.right;
                    }
                } else { // if both childs are null then just return
                    return;
                }
            }
            connect(root.right); // recur to the right child first, because children of left child are going to point to the children of the right one
            connect(root.left); // finally recur to the left child
        }
    }

Log in to reply
 

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