LeetCode 풀기 - 897. Increasing Order Search Tree

897. Increasing Order Search Tree

https://leetcode.com/problems/increasing-order-search-tree/

Increasing Order Search Tree - LeetCode

문제)

 

솔루션1) - inorder traversal, insert

3 steps로 풀이를 접근 하였습니다.

 

1) 기존 노드르 inorder traversal 수행해서 정렬된 numbers를 리스트 형태로 유지

2) 정렬된 numbers의 첫번째 값(가장 작은 값)으로 새로운 노드를 하나 생성

3) 새로운 노드가 새로운 트리의 root가 되고 해당 루트의 나머지 numbers의 값들은 insert node 처리

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def increasingBST(self, root):
        if root is None:
            return root

        # inorder 순회회서 정렬된 val을 리스트 형태 표현
        values = deque()
        self.inorder(root, values)

        # 새로운 노드의 루트를 가장 작은 값으로 노드 생성
        new_root = TreeNode(values.popleft())

        # 순회해면서 새로운 트리에 insert
        for val in values:
            self.insert(new_root, val)

        return new_root
    
    def inorder(self, node, values):
        if node is None:
            return

        self.inorder(node.left, values)
        values.append(node.val)
        self.inorder(node.right, values)

    def insert(self, node, val):
        if node is None:
            return TreeNode(val)

        if node.val < val:
            node.right = self.insert(node.right, val)
        elif node.val > val:
            node.left = self.insert(node.left, val)

        return node

솔루션2)

솔루션1)에서는 재귀적으로 tree를 구성하도록 함수를 만들었습니다.

하지만, 굳이 이렇게 구현할 필요가 없습니다.

이미 정렬된 배열 형태의 number가 있기 때문에 순차적으로 노드를 생성하면서 계속 오른쪽에 자식 노드를 추가하면 됩니다.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def increasingBST(self, root):
        if root is None:
            return root

        # inorder 순회회서 정렬된 val을 리스트 형태 표현
        values = deque()
        self.inorder(root, values)
        
        new_root = TreeNode(None)
        cur = new_root
        
        # 오른쪽에 자식 노드를 계속 추가
        for val in values:
            cur.right = TreeNode(val)
            cur = cur.right        

        return new_root.right
    
    def inorder(self, node, values):
        if node is None:
            return

        self.inorder(node.left, values)
        values.append(node.val)
        self.inorder(node.right, values)