99클럽 코테 스터디 18일차 TIL (Increasing Order Search Tree) - LeetCode

이번주 내내 몸이 너무 안좋다.. 중요한 시기에 몸이 이러니,,, 그래도 조금씩이라도 진행해보자.. 1문제와 TIL은 꼭 진행한다..

---

1. 오늘의 학습 키워드

• 이진 트리
• BST
• DFS
• 중위순회
• Inorder traversal

---

2. 문제: 897. Increasing Order Search Tree

• 단계: Easy
• 주제: Stack, Tree, Depth-First Search, Binary Search Tree, Binary Tree
• 출처: https://leetcode.com/problems/increasing-order-search-tree/

문제 설명

Given the root of a binary search tree, rearrange the tree in in-order so that the leftmost node in the tree is now the root of the tree, and every node has no left child and only one right child.

Example 1:

Input: root = [5,3,6,2,4,null,8,1,null,null,null,7,9]
Output: [1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]

Example 2:

Input: root = [5,1,7]
Output: [1,null,5,null,7]

Constraints:

• The number of nodes in the given tree will be in the range [1, 100].
• 0 <= Node.val <= 1000

---

3. 나의 풀이

접근 방법

이 문제는 BST에 root 노드가 주어졌을 때, 중위 순서(in-order)대로 재배열하여 트리의 가장 왼쪽 노드가 새로운 루트가 되게 하고, 모든 노드가 왼쪽 자식이 없고 오직 하나의 오른쪽 자식만 가지도록 하게 하는 문제이다.

따라서, return되는 결과는 배열이나 링크드 리스트의 형태를 원하는 것이다.

어제 TIL에서도 중위순회 문제였기 때문에 비교적 처음에 쉽게 접근하였다.

중위 순회는 루트 노드의 왼쪽 서브 트리 → 루트 노드 → 루트 노드의 오른쪽 서브 트리 순으로 순회하는 방식이다.

코드 구현은 아래와 같다.

# Definition for a binary tree node.
class TreeNode(object):
    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 not root:
        return    
    def inorder(root,res): # 중위 순회 (inorder)
        if not root:
            return
        inorder(root.left,res)
        res.append(root.val)
        inorder(root.right,res)
        return res
    

inorder 메서드에서 res는 중위 순회를 통해 탐색되는 노드들을 담는 리스트 타입의 변수이다.

이렇게 진행하면 중위 순회 코드는 완성이 된다.

현재 우리는 이 문장까지 완성한 것이다.

• 우리가 문제를 다시 돌아보면, 중위 순서대로 재배열하여

여기서 더 나아가서 다음 문장을 본다면?

”트리의 가장 왼쪽 노드가 새로운 루트가 되게하고,,,”

이 문장은 다음과 같이 구현할 수 있다.

# Definition for a binary tree node.
class TreeNode(object):
    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 not root:
        return    
    def inorder(root,res):
        if not root:
            return
        inorder(root.left,res)
        res.append(root.val)
        inorder(root.right,res)
        return res
    array = inorder(root,[]) 
    new_root = TreeNode(array[0])

array라는 리스트에 중위 순회 결과를 담는다. 그 다음 array 리스트의 첫번째값 (루트 노드)을 new_root라는 변수에 TreeNode 클래스를 통해 인스턴스를 생성한다.

이렇게 되면 new_root는 BST에 root 노드가 주어졌을 때, 중위 순서(in-order)대로 재배열하여 트리의 가장 왼쪽 노드가 새로운 루트가 되는것이다.

그 다음 문제를 보면 “모든 노드가 왼쪽 자식이 없고 오직 하나의 오른쪽 자식만 가지도록 하게 하라” 라는 문장이다.

이것은 단순히 생각하면 “순차적으로 나열되는 자료 구조를 활용하여 중위 순회 결과를 return하라. 그리고 TreeNode객체를 활용할 때, right 인자를 활용하라.” 라고 해석할 수 있다.

따라서, new_root와 동일한 값을 참조 하도록 current 변수를 도입한다. 도입하는 방식은 아래와 같다.

current = new_root

그렇다면 current는 new_root의 값을 가리키게 되고, 노드 객체 TreeNode를 통해 current 노드의 오른쪽 노드에 값을 할당하게 된다.

코드는 다음과 같다.

for i in range(1,len(array)):
        current.right = TreeNode(array[i])
        current = current.right

만약 current 변수에 new_root를 할당하지 않고, new_root을 바로 위 코드처럼 반복문을 돌리게 되면, new_root에는 마지막 최종 노드만이 나오게 된다.

최종 코드는 아래와 같다.

# Definition for a binary tree node.
class TreeNode(object):
    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 not root:
        return    
    def inorder(root,res):
        if not root:
            return
        inorder(root.left,res)
        res.append(root.val)
        inorder(root.right,res)
        return res
    array = inorder(root,[])
    new_root = TreeNode(array[0])
    current = new_root
    for i in range(1,len(array)):
        current.right = TreeNode(array[i])
        current = current.right
    
    return new_root

위 코드의 결과를 보기 위해 예시를 만들어 보았다.

# 897. Increasing Order Search Tree

# Definition for a binary tree node.
class TreeNode(object):
    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 not root:
        return    
    def inorder(root,res):
        if not root:
            return
        inorder(root.left,res)
        res.append(root.val)
        inorder(root.right,res)
        return res
    array = inorder(root,[])
    new_root = TreeNode(array[0])
    current = new_root
    for i in range(1,len(array)):
        current.right = TreeNode(array[i])
        current = current.right
    
    return new_root

# Helper function to print the tree in order
def print_tree(root):
    current = root
    while current:
        print(current.val, end=" -> ")
        current = current.right
    print("Done")

# Example1
root = TreeNode(5)
root.left = TreeNode(3)
root.right = TreeNode(6)
root.left.left = TreeNode(2)
root.left.right = TreeNode(4)
root.left.left.left = TreeNode(1)
root.right.right = TreeNode(8)
root.right.right.left = TreeNode(7)
root.right.right.right = TreeNode(9)

# Create the solution object
solution = Solution()

# Get the result of increasingBST
result = solution.increasingBST(root)

# Print the result
print_tree(result) # 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> Done

---

4. 결과

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

---

5. 결론

오늘 문제는 어제문제에서 조금 더 업그레이된 문제이다. 중위 순회 결과를 잘? 보여지게 만드는 내용까지 추가되었기 때문에 약간 고생을 한 것 같다. 아무래도 현재 컨디션이 좋지 않아,, 좀 오래 걸렸다.

빨리 회복하자!

읽어주셔서 감사합니다.