O(1) space solution


  • -7
    B
    public class Solution {
    public void connect(TreeLinkNode root) {
        if (root == null) return; // simple
        if (root.left == null && root.right == null) return; // simple
        TreeLinkNode last = root.right; if (last == null) last = root.left; 
        // last means the rightest of the existing sons.
        // first means the leftest of the sons of right brothers of the root.
        TreeLinkNode first = root.next; 
        while (true) {
            if (first == null) break;
            //as far as somne of our right brothers has children we shoudl link our last with it.
            if (first.left != null) {
                last.next = first.left; 
                break;
            }
            if (first.right != null) {
                last.next = first.right;
                break;
            }
            first = first.next;
        }
        // linking our childrens if both exists
        if (root.left != null && root.right != null) {
            root.left.next = root.right;
        }
        
        connect(root.right);
        connect(root.left);
    }

  • 3
    J

    Not O(1) space complexity. The recursive call uses additional memory proportional to the height of the tree.


  • 0
    W

    if it's recursive, it's never space O(1)


  • 0
    Y
    public class Solution {
    public void connect(TreeLinkNode root) {
        TreeLinkNode start=root;
        TreeLinkNode p=null;
        TreeLinkNode q=null;
        
        while(start!=null){ 
            if(start.left==null && start.right==null){ // start node indicates the first non-leaf node of current level being processing.
                start=start.next;
                continue;
            }
            p=start; // Begin from start node, node p and node q finish the connect task of next level.
            while(p!=null){  
                q=p.next;  /* node q is the next non-leaf node right after p*/
                while(q!=null && q.left==null && q.right==null){
                    q=q.next;
                }
                if(q==null){ // this means no other non-leaf node left, just finish connect node p's children
                    if(p.left!=null && p.right!=null)
                        p.left.next=p.right;
                }
                else{ 
                    if(p.left!=null && p.right!=null){
                        p.left.next=p.right;
                        p.right.next=(q.left!=null)?q.left:q.right;
                    }
                    else if(p.left==null && p.right!=null){
                        p.right.next=(q.left!=null)?q.left:q.right;
                    }
                    else{
                        p.left.next=(q.left!=null)?q.left:q.right;
                    }
                }
                p=q; 
            }
            start=(start.left!=null)?start.left:start.right; // start node goes to first non-leaf node of next level and repeat the above process
        }
    }
    

    }


  • 0
    Y

    This is O(1) space solution


Log in to reply
 

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