Constant Space Accepted Solution, and any other ideas?


  • 3
    M

    I have implement an algorithm about these problem by using a FIFO queue, but it costs extra space, so I have come up with a solution which only costs constant space, this solution takes the advantages of the next pointed we created. The code below will help you understand better about my solution, and if you have any other good ideas, please share it.

    /*Step 1: linkNull. After this step the tree will be like the following:
         1 -> NULL
       /  \
      2    3 -> NULL
     / \  / \
    4  5 6   7 -> NULL
    
    Step 2: linkChildren. After this step the tree will be like the following:
         1 -> NULL
       /  \
      2 -> 3 -> NULL
    / \  / \
    4-> 5 6->7 -> NULL
    Notice the Node5 and Node 6 has not linked together
    
    Step 3: linkTheLeft. After this step the tree will be like the following:
         1 -> NULL
       /  \
      2  -> 3 -> NULL
     / \   / \
    4-> 5->6->7 -> NULL
    This step takes the advantages of the next pointer we have created in the step 2 and step 3
    */
    
    public class Solution {
    public void connect(TreeLinkNode root) {
        if(root == null)
            return;
        linkNull(root); // Link all the right most node at every level to null
        linkChildren(root); // Link the children of all non-leave nodes
        if(root.left != null)
            linkTheLeft(root.left); // Link all the nodes left which has not linked to its right neighbor node
        
    }
    public void linkNull(TreeLinkNode root) {
        if(root.right == null)
            return;
        root.next = null;
        linkNull(root.right);
    }
    public void linkChildren(TreeLinkNode root) {
        if(root.left == null && root.right == null)
            return;
        root.left.next = root.right;
        if(root.left != null)
            linkChildren(root.left);
        if(root.right != null)
            linkChildren(root.right);
    }
    public void linkTheLeft(TreeLinkNode root) {
        while(root.left != null && root.right != null) {
            TreeLinkNode pre = root;
            TreeLinkNode cur = pre.next;
            while(cur != null) {
                pre.right.next = cur.left;
                pre = cur;
                cur = pre.next;
            }
            root = root.left;
        }
        
    }
    

    }


  • 1
    S

    That's way more complicated than necessary, and not actually constant space. But your explanation of what you're doing is excellent.


    Step 1: You don't need to do that, all of the next pointers start out null. Wastes log(n) time on unnecessary operations and log(n) space on recursion stack frames. (The space is trivial to recover by switching to iteration... but you don't need to do this anyway.)

    Step 2: Links only siblings, not cousins. Spends n time and log(n) space for the trivial half of a solution. Not great, but it's a start. Note that since the tree is guaranteed to be perfect you don't need to test for each child separately, every node has both or neither.

    Step 3: Finally links the cousins. Spends n time and constant space for the nontrivial half of a solution. This is almost good; I wonder if you read the hint about using the next links and added this to fill what was missing. Again you don't need to test for each child separately; not only does each node have both or neither, each row has all or none - which you actually use here, by only testing for the children of the first node in each row.


    The thing that jumps out at me from that is that you're using log(n) space for the trivial part, and constant space for the nontrivial part. The reason is that the nontrivial part must be iterative, and the obvious approach to the trivial part must be recursive. The key thing you're missing is that the trivial part, being trivial, can be rolled in to the nontrivial part. The entire solution can be a modification of linkTheLeft.


Log in to reply
 

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