노트
- 트리 탐색은 preorder, inorder, postorder
- nonlocal 변수 활용으로 이전 노드 기억하기
- binary search tree의 가장 왼쪽은 가장 작은값, 가장 오른쪽은 가장 큰값
- 가장 작은 노드를 기억하기 위해 nonlocal 변수 활용
"""
# Definition for a Node.
class Node:
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right
"""
class Solution:
def treeToDoublyList(self, root: 'Node') -> 'Node':
def inorder(root):
nonlocal last, first
if root:
inorder(root.left)
if last:
last.right = root
root.left = last
else:
first = root
last = root
inorder(root.right)
if not root:
return None
last, first = None, None
inorder(root)
first.left = last
last.right = first
return first
