Is this Accept solution use the constant extra space?


  • 0
    C

    My solution is accepted, but I'm not very sure the solution use constant extra space, anyone help?

    public class Solution {
    public void connect(TreeLinkNode root) {
        if (root == null) return;
    
        ArrayList<TreeLinkNode> l = new ArrayList<TreeLinkNode>();
        l.add(root);
    
        while(!l.isEmpty()) {
            ArrayList<TreeLinkNode> l2 = new ArrayList<TreeLinkNode>();
            for(int i=0; i< l.size(); i++) {
                TreeLinkNode node = l.get(i);
                
                if (i != l.size()-1) node.next = l.get(i+1);
                else node.next = null;
    
                if (node.left != null) l2.add(node.left);
                if (node.right != null) l2.add(node.right);
            }
    
            l = l2;
        }
    }
    

    }


  • 0
    P

    your answer is a typical BFS, and the memory usage of those two arraylists makes your solution uses log(N) space instead of constant space.


Log in to reply
 

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