[LeetCode] 116 | Populating Next Right Pointers in Each Node | Python

---

문제 링크: https://leetcode.com/problems/populating-next-right-pointers-in-each-node/

---

문제

You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

---

조건

• The number of nodes in the tree is in the range [0, 212 - 1].
• -1000 <= Node.val <= 1000

---

내 풀이

이 두가지 생각으로 해당 문제를 풀 수 있다.

left의 next는 항상 right다.

right의 next는 root의 next의 left다.

---

코드

class Solution:
    def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':
        self.comes(root)
        return root
        
    def comes(self, root):
        if not root:
            return
        
        if root.left:
            root.left.next = root.right
            
            if root.next:
                root.right.next = root.next.left
            else:
                root.right.next = None
        
        self.comes(root.left)
        self.comes(root.right)