May LeetCoding Challenge[Day20] - Kth Smallest Element in a BST

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.

Input: root = [3,1,4,null,2],
k = 1
   3
1   4 
  2

Output: 1

1. 알고리즘을 해결하기 위해서 생각한 방법

 

 - BST가 주어질 때, k번째로 작은 숫자를 찾는 문제

 - 잘 모르겠으니, 보고 풀어보자.

 

https://www.youtube.com/watch?v=xBkzsYbLjAA

 

2. 알고리즘 작성 중, 어려운 점 & 깨달은 점

 

- 어느 정도, 재귀함수를 사용해서 풀으려고 했는데, 답을 찾고 어떻게 return 해야할 지, 카운트를 어떤 방식으로 누적해야할 지, 왼쪽과 오른쪽 노드로 이동할 때, 체크해야하는 로직을 잘 몰랐다.

 

- inorder traversal, 책에서만 항상 봤던 중위 순회를 실제로 구현할 수 있는 기회였다.

 왼쪽 자식노드, 가운데 노드, 오른쪽 자식 노드로 순회를 하는 방식이고, 해당 순회를 했을 때 작은 숫자부터 나열된다는 것을 알 수 있었다.

 

3. 내가 작성한 알고리즘

 

 

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int kthSmallest(TreeNode root, int k) {
        int answer = exploreNode(root, k, new int[]{0});
        return answer;
    }
    
    //find the smallest O(H), h = height of the binary search tree
    //O(H+k)
    public int exploreNode(TreeNode node, int k, int[] kth){
        if(node.left != null){
            int left=  exploreNode(node.left, k, kth);    
            if(kth[0] == k) return left;
        }
        
        kth[0]++;
        if(kth[0] == k){
            return node.val;
        }
        
        if(node.right != null){
            int right = exploreNode(node.right, k, kth);
            if(kth[0] == k) return right;
        }
        return -1;
    }
    
}

 

4. 결과

 

문제 : https://leetcode.com/explore/challenge/card/may-leetcoding-challenge/536/week-3-may-15th-may-21st/3335/

Explore - LeetCode