230. Kth Smallest Element in a BST

문제 링크: https://leetcode.com/problems/kth-smallest-element-in-a-bst/description/?envType=study-plan-v2&envId=top-interview-150

문제

BST의 root 노드가 주어진다. k번째로 작은 값을 반환하자.

입력

• BST의 root 노드
• 정수 k

출력

• BST에서 k번째로 작은 값

---

나의 풀이

접근

BST 중위 순회를 이용한다면, 오름차순으로 정렬이 되어 있는 배열을 반환하는 사실을 이용하려고 했다.

count 값을 전역변수로 두고, 하나씩 증가시켜 k와 같다면 해당 노드의 값을 반환하려고 했지만, 너무 복잡하게 코드를 짜느라 오히려 구현하지 못했다.

시간을 너무 소요했기 때문에 다른 풀이를 보려고 한다.

---

다른 풀이

사실 알고리즘 문제에서 전역 변수를 사용하는 것은 지양한다고 한다.

앞서 내가 접근했던 방법은 사실 전역변수를 사용하는 방법이라 다른 풀이를 찾아보았다.

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

• stack에 root의 하위트리의 모든 left 노드를 저장한다
• k가 0이 될 때까지 아래를 반복
  • stack에서 꺼내온 후, k를 감소시킨다
  • 만약 k가 0이라면 해당 노드를 반환
  • 해당 노드의 오른쪽 노드를 탐색하기 위해, 오른쪽 노드의 왼쪽 하위 노드들을 다시 스택에 저장

전역변수 대신, 스택을 이용해 해당 문제를 해결해나갔다는 점이 좋았다.