LeetCode : 230. Kth Smallest Element in a BST

문제 링크

문제 먼저 읽기

• 이진 검색 트리의 루트와 정수 k가 주어졌습니다.
• 트리에 있는 모든 노드의 값 중 K번째 가장 작은 값(1-indexed)을 반환합니다.

어떻게 풀까?

생각

• root로부터 맨 왼쪽에 위치한 값이 제일 작은 값입니다.
• 거기서부터 시작해서 이전 노드, 오른쪽 노드 순서대로 탐색할 수 있는 재귀함수를 만듭니다.

수도코드

class Solution {
    
    int count = 0;
    int result = 0;
        
    public int kthSmallest(TreeNode root, int k) {
        count = k;
        search(root);
        return result;
    }
    
    public void search(TreeNode node) {
        if (node == null) return ;
        
        search(node.left); // 맨 왼쪽으로 이동
        
        count --; // 중앙값
        if (count==0) {
            result = node.val;
            return;
        }
        
        count --; // 오른쪽 값 확인
        search(node.right);
    }
}

• 위 수도코드는 다음의 tesetcase에서 실패합니다.

Input
[5,3,6,2,4,null,null,1]
3
Output
2
Expected
3

• 오른쪽 값 확인을 하기전에 count —; 를 다시 해준게 노드를 뛰어 넘게 된 것입니다.

class Solution {
    
    int count = 0;
    int result = 0;
        
    public int kthSmallest(TreeNode root, int k) {
        count = k;
        search(root);
        return result;
    }
    
    public void search(TreeNode node) {
        if (node == null) return ;
        
        search(node.left); // 맨 왼쪽으로 이동
        
        if (--count==0) {
            result = node.val;
            return;
        }
        
        search(node.right);
    }
}

결과

<aside> 💡 Success

Details

Runtime: 0 ms, faster than 100.00% of Java online submissions for Kth Smallest Element in a BST.

Memory Usage: 44.2 MB, less than 35.62% of Java online submissions for Kth Smallest Element in a BST.

</aside>

다른 풀이 방식과 문제 회고

class Solution {
    public int kthSmallest(TreeNode root, int k) {
     Stack<TreeNode> stack = new Stack<>();
     while(root != null || !stack.isEmpty()) {
         while(root != null) {
             stack.push(root);    
             root = root.left;   
         } 
         root = stack.pop();
         if(--k == 0) break;
         root = root.right;
     }
     return root.val;
 }
}

• stack으로 푸는 방식이 특이했습니다.
• 트리를 순회하며 값을 넣고 빼는 것으로 공간복잡도를 최소화 한 것 같습니다.