[Leetcode] 116. Populating Next Right Pointers in Each Node

21-11-27
solved in a poor way

Problem

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.

BST의 각 노드에서 B+ Tree Leaves들처럼 next Pointer 만드는 문제이다.

Solution

class Solution:
    def connect(self, root: 'Node') -> 'Node':
          
        if not root:
            return root
        h=1
        trav=root
        while trav.right:
            trav=trav.right
            h+=1
        print(h)
        
        ary=[None]*h
      
        
        def goDFS(node,depth,ary):
            node.next=ary[depth]
            
            if not node.right:
                return
            
            goDFS(node.right,depth+1,ary)
            ary[depth+1]=node.right
            
            goDFS(node.left,depth+1,ary)
            ary[depth+1]=node.left
        
        goDFS(root,0,ary)
        
        
        return root

ary i번째 원소는 가장 최근 다나간 i번째 node를 저장한다. 그래서 goDFS에 들어가자 마자, node.next=ary[depth]로 간단하게 nextPointer를 찾을 수 있다.
처음에 아이디어가 떠오르지 않다가. 재귀함수를 호출하고 난뒤, ary를 업데이트하는 아이디어가 떠올라서, 문제를 해결할 수 있었다. 즉 탐색을 완료한 다음에, 다음 같은 depth에 있는 노드를 탐색할 때, 완료한 노드를 참조할 수 있도록 ary를 업데이트하는 것이다.

하지만 1)Space Complexity를 O(1)으로 맞추지 못했고, h를 미리 알아야하기 때문에 2)시간도 h만큼 더 경과했다.
(마지막 solution은 딕셔너리 이용해서 높이 몰라도 되게 해뒀다.)

BestSolution

Recursion

def connect(self, root):
    def trav(root):
        if not root.left and not root.right:
            return
        if not root.next:
            root.left.next = root.right
            root.right.next = None
        else:
            root.left.next = root.right
            root.right.next = root.next.left
        trav(root.left)
        trav(root.right)
    if not root:
        return
    root.next = None
    trav(root)

제일 중요한 코드

root.right.next=root.next=left

와우...
이런건 관찰하면 보일까? 생각도 못했다. root의 next를 이용해서 root.right의 nextPointer를 결정했다. 그림을 더 잘 봐야했나?

Similiar,but better Solution