leetcode medium : Populating next right pointers in each node

https://leetcode.com/problems/populating-next-right-pointers-in-each-node/

Populating Next Right Pointers in Each Node - LeetCode

 

되게 쉬운문제다.

이게 왜 medium인진 잘 모르겠음

일단 left subtree의 next가 right subtree의 left를 가리키게 해야되는건 무조건이다.

문제는 left subtree의 right subtree의 노드가 어디를 가리키냐인데

현재노드(root)에 next가 있을때 root.right.next = root.next.left로 하면 된다.

 

class Solution {
    public Node connect(Node root) {
        if(root!=null && root.left!=null){
            root.left.next = root.right;
            if(root.next!=null){
                root.right.next = root.next.left;
            }
            
            connect(root.left);
            connect(root.right);
        }
        
        return root;
    }
}

 

파이썬으로 채점이 잘 안돼서 자바로 풀었다.

공간복잡도는 recursive call을 썼으므로 O(log N), 재귀 스택 제외하면 O(1)

시간복잡도는 O(N)이다

 

다른 사람 솔루션을 볼까?

 

class Solution(object):
    def connect(self, root):
        """
        :type root: TreeLinkNode
        :rtype: nothing
        """
        
        if not root:
            return None
        cur  = root
        next = root.left

        while cur.left :
            cur.left.next = cur.right
            if cur.next:
                cur.right.next = cur.next.left
                cur = cur.next
            else:
                cur = next
                next = cur.left

 

다음 레벨의 첫 노드를 next에 저장해두고 해당 레벨을 cur로 쭉 돌아가면서 작업하는 방식이다.

진짜 O(1) Constant space solution이네! ㄸㄸㄸㄷ 대단하다.. 기발하네 진짜