Share my simple Java Recursive Solution


  • 0
    J

    Nothing fancy, just level order traversal, we are Spurs! We play fundamental basketball!

    public void connect(TreeLinkNode root) {
        if (root == null) return;
        
        List<TreeLinkNode> list = new ArrayList<TreeLinkNode>();
        list.add(root);
        traverse(list);
    }
    
    private void traverse(List<TreeLinkNode> list) {
        if (list.size() == 0) return;
        
        List<TreeLinkNode> next = new ArrayList<TreeLinkNode>();
        
        for (int i = 0; i < list.size(); i++) {
            TreeLinkNode node = list.get(i);
            if (i != list.size() - 1)  {
                node.next = list.get(i + 1);
            }
            
            if (node.left != null) next.add(node.left);
            if (node.right != null) next.add(node.right);
        }
        traverse(next);
    }

  • 0
    S

    Your code is not constant space. You store nodes for each layer. Space complexity should be O(logn).

    But I think you could modify to achieve that. Use the next pointer to traversal through a layer instead of extra List.


  • 0
    J

    can you explain a little more about how to lower the space complexity by "Use the next pointer to traversal through a layer instead of extra List"?


  • 0
    L

    Recursion here is not necessary. Since you use ArrayList, your code can be improved by using while or for loop.


  • 0
    S

    Notice this. You use list to store all nodes in current layer in order to traversal them and then next layer. Notice the next pointer is actually linking each node in current layer. If you want to traversal current layer, call node.next like you traversal a linked list.


Log in to reply
 

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