426. Convert Binary Search Tree to Sorted Doubly Linked List ()

링크 - https://leetcode.com/problems/convert-binary-search-tree-to-sorted-doubly-linked-list/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days

난이도 - Medium

Intuition

우리는 BFS를 통해서 이 문제를 풀 수 있다. 먼저 값 순서대로 sorting을 해야 하므로 left -> node -> right순으로 노드를 탐색해야 한다. 그리고 우리는 first와 last를 추적해서 마지막에 연결을 하고 또한 last는 매 단계마다 이전 node를 알수 있게 해주므로 연결을 해줄 수 있다.

Code

"""
# 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: 'Optional[Node]') -> 'Optional[Node]':
        first, last = None, None
        def dfs(node):
            if not node:
                return

            dfs(node.left)

            nonlocal first, last
            if last:
                last.right = node
                node.left = last
            else:
                first = node
            last = node

            dfs(node.right)

        if not root:
            return None

        dfs(root)

        first.left = last
        last.right = first
        return first

Complexity

Time Complexity: O(N)

Space Complexity: O(N)