Share my clean AC recursive java solution, 225 ms


  • 0

    Don't know if my code takes o(1) memory, cause it is recursive. It should take some space. But, it is accepted anyway and fast in java codes.

    My algorithm has 2 step:

    1. For all levels except last one, for every node connect its left to its right using left's next pointer.

    2. Then, draw on paper, you would find the left arrows for next are only related to those node who already has next pointer connected. Relation is root.right.next = root.next.left;

    Therefore, just recursive twice. So I bet the complexity is O(2) = O(1).

    public void connect(TreeLinkNode root) {
        sub1(root);
        sub2(root);
    }
    
    protected void sub1(TreeLinkNode root){
        if(root == null || root.left == null) return;
        root.left.next = root.right;
        sub1(root.left);
        sub1(root.right);
    }
    
    protected void sub2(TreeLinkNode root){
        if(root == null || root.left == null) return;
        if(root.next != null) root.right.next = root.next.left;
        sub2(root.left);
        sub2(root.right);
    }

Log in to reply
 

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