leetcode medium : Populating Next Right Pointers in Each Node II

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

Populating Next Right Pointers in Each Node II - LeetCode

 

 

어우 이건 시간 내에 못풀었다.

꽤어렵네..

 

발상했는데 구현은 못한 재귀적인 방법

public Node connect(Node root) {
        if (root == null) return null;
        
        if (root.left != null) { // update left next
            if (root.right != null) root.left.next = root.right; // if right child exists - simple connect left.next to right
            else root.left.next = findNext(root); // if not - scan parent next node until we find the first left or right child
        }
        if (root.right != null) { // update right next
            root.right.next = findNext(root);
        }
        
        connect(root.right); // update the right nodes first
        connect(root.left);
        return root;
    }
    
    private Node findNext(Node root) { // get parent node
        while (root.next != null) { // scan all next parent nodes until we find the first left or right child
            root = root.next;
            if (root.left != null) return root.left;
            if (root.right != null) return root.right;
        }
        return null;
    }

파이썬 버전으로 직접 풀어봤다.

"""
# Definition for a Node.
class Node:
    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next
"""

class Solution:
    def find_next(self, root):
        while root.next:
            root = root.next
            if root.left:
                return root.left
            if root.right:
                return root.right
        return None
    
    def connect(self, root: 'Node') -> 'Node':
        if not root:
            return None
        
        if root.left and root.right:
            root.left.next = root.right
            root.right.next = self.find_next(root)
        if root.left and not root.right:
            root.left.next = self.find_next(root)
        if not root.left and root.right:
            root.right.next =self.find_next(root)
        
        self.connect(root.right)
        self.connect(root.left)
        return root

 

이해가 안되는 간단한 반복문 솔루션

def connect(self, node):
    tail = dummy = TreeLinkNode(0)
    while node:
        tail.next = node.left
        if tail.next:
            tail = tail.next
        tail.next = node.right
        if tail.next:
            tail = tail.next
        node = node.next
        if not node:
            tail = dummy
            node = dummy.next

ㅇ 

아아아아 이해됐다. 이건 위에서부터 아래 레벨의 next를 처리해가는 방법인데 dummy는 제일 왼쪽에 있는 노드를 next로 가리킬 가상의 노드다. 맨 왼쪽에 있는 가상의 노드.

아아.. 천재인가 이 솔루션 만든사람.. ㄸ