[Leetcode Top Interview 150] 230. Kth Smallest Element in a BST

난이도 : medium

문제링크

• binary search tree의 root 노드와 int k 값이 주어진다
• k번째로 작은 값의 노드를 리턴하라

1. 접근법

• 중위표현식으로 탐색하면 오름차순으로 탐색이 가능하다
• k번째 값을 리턴

 

2. 의사코드

count = 0;

if (count == k) {
	return root.val;
}

int ans = Dfs(root.left);
if (ans != Integer.MAX_VALUE) {
	return ans;
}

count++

if (count == k) {
	return root.val;
}

return Dfs(root.right);

•  

 

3. 구현 코드

class Solution {
    int count = 0;
    public int kthSmallest(TreeNode root, int k) {
        if (root == null) {
            return Integer.MAX_VALUE;
        }
        
        int temp = kthSmallest(root.left, k);

        if (temp != Integer.MAX_VALUE) {
            return temp;
        }

        count++;
        if (count == k) {
            return root.val;
        }

        return kthSmallest(root.right, k);
    }
}

• 노드에서 count값이 k값과 같다면 왼쪽 노드값 리턴

 

4. 시간복잡도, 공간복잡도 예상

• 시간복잡도 : O(n) - 최악의 경우, 전체 노드를 방문해야 함
• 공간복잡도 : O(1) - 상수 크기만 사용함

 

5. 개선점

• 잘 모르겠다

 

6. 회고

class Solution {    
    public int kthSmallest(TreeNode root, int k) {
        int n = 0;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;        

        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }

            cur = stack.pop();
            n += 1;
            if (n == k) {
                return cur.val;
            }

            cur = cur.right;
        }
        
        return 0;
    }
}

(출처: NeetCode_youtube)

• 중위표현식을 스택을 이용하여 구현했다
• 오른쪽 노드가 존재한다면 반복하여 스택에 노드 저장
• 이렇게도 할수 있구나