"You may only use constant extra space." - So does it mean we cannot use recursion?


  • 13
    Q

    Does anyone have an iteration method with constant space solution?


  • 68
    S

    Here is solution from old discuss by skaugust. Thanks to skaugust!

    I'm confused why people are trying to use recursive solutions here. The problem states that you can only use constant space. To get to the leaf nodes, a recursive solution needs to be log2(n) calls deep, and each call has a call stack, which takes up memory. This means that a recursive solution isn't constant memory, but O(log(n)) memory. To solve this, you just replace the recursive call with a while loop wrapping all of your logic.

    /* Go through parent level by its next pointer to generate children level next pointer */
    public class Solution {
        public void connect(TreeLinkNode root) {
            
            TreeLinkNode leftWall = root;
            while (leftWall != null) {
    
                TreeLinkNode across = leftWall;
                while (across != null) {
                    if (across.left != null) {
                        across.left.next = across.right;
                    }
    
                    if (across.right != null && across.next != null) {
                        across.right.next = across.next.left;
                    }
    
                    across = across.next;
                }
                leftWall = leftWall.left;
            }
        }
    }

  • 0
    Q

    But from my opinion, recursive solution is much clear and easier. if n = 2^64, log(n) is just 64. I think log(n) makes no big difference to a constant.


  • 0
    S

    Hi qiqjiao. The recursive solution would be log2n deep. This does not necessarily mean that the space complexity is O(log2n).


  • 0
    H

    any size changing with respect to n is not constant space!


  • 0
    S

    Since the tree is guaranteed to be complete, you don't have to test for the existence of each child, just make your outer loop condition ( leftWall != null && leftWall.left != null ).


  • 0
    Q

    recursive is guaranteed to not be a constant space solution!


  • 0
    P
    This post is deleted!

Log in to reply
 

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