230. Kth Smallest Element in a BST

https://leetcode.com/problems/kth-smallest-element-in-a-bst/

Kth Smallest Element in a BST - LeetCode

Solution

class Solution:
    def kthSmallest(self, root, k):
        def rank(node, ans):
            if node.left and rank(node.left, ans):
                return True

            ans.append(node.val)
            if len(ans) == k:
                return True

            if node.right and rank(node.right, ans):
                return True
            
            return False

        ans = []
        rank(root, ans)
        return ans[-1]

• rank는 재귀로 실행되며 노드의 순서에 맞게 value를 ans 리스트에 넣어준다.
• node.left가 존재하면 rank()가 실행된다.
• rank()가 True를 반환하면 True를 반환한다.
  • 이렇게 하는 이유는 간결함을 위해서이다.
  • node.left 존재한다면 -> rank() True 반환하면 -> True 흘려보내기
  • 위의 과정은 if문 2개를 중첩하게 되고, and를 사용하여 더 편하게 하였다.
  • 간단하게 node.left가 존재할 때 rank()가 항상 실행되어서 괜찮다.
• rank()가 False를 반환하면 현재 노드의 value가 ans에 추가된다.
• ans의 길이가 k와 같다면 True를 반환한다. 이 True가 계속 타고 올라가면서 불필요한 노드의 계산을 하지 않아도 된다.
• node.right가 존재하면 rank()가 실행되고, rank()가 True를 반환하면 True를 반환한다.
• 마지막에 False를 반환한다.

class Solution:
    def kthSmallest(self, root, k):
        def rank(node, ans):
            if not node:
                return False

            if rank(node.left, ans):
                return True

            ans.append(node.val)
            if len(ans) == k:
                return True

            if rank(node.right, ans):
                return True
            
            return False

        ans = []
        rank(root, ans)
        return ans[-1]

• 같은 방식이다.
• 노드를 검사하고 함수에 집어넣는게 아니라, 일단 넣고 함수 안에서 None인지 아닌지 검사한다.

Another

class Solution:
    def kthSmallest(self, root, k):
        stack = []
        rank = 0
        node = root
        while stack or node:
            while node:
                stack.append(node)
                node = node.left
            
            node = stack.pop()
            rank += 1
            if rank == k:
                return node.val
            node = node.right

• 재귀를 사용하지 않고 스택을 사용한다.
• while문으로 stack이 빌때까지 계속하고, 처음 들어갈 때 stack이 비어있는 것을 고려하여 node도 조건에 넣는다.
• 두번째 while문은 현재 노드로부터 가장 왼쪽으로 가고, 가는 길마다 노드를 스택에 넣는다.
• 가장 왼쪽에 도달하면 끝의 노드를 꺼낸다.
• 기존 순서로부터 1을 증가시키고 k인지 확인하고, 맞으면 반환한다.
• 아니면 그 끝의 오른쪽 자식으로 넘어간다. 만약 자식이 없다면 두번째 while을 지나 스택에서 하나 꺼내게 된다.

 

• 정리하면 현재 노드에서 가장 왼쪽으로 가고 1증가.
• 오른쪽 자식으로 갔다가 다시 왼쪽 끝으로 1증가.
• 오른쪽이 없게 되면 스택에서 하나 꺼내게 되면서 위로 올라가게 된다.