.leetcode(230. Kth Smallest Element in a BST)

문제

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

문제 풀기 전

1. kth 나오자 마자 bst는 보지못하고 priorityQueue라고 생각하였다.
2. 순회해서 다 저장하고 priorityQueue로 해결할 수 있겠다.
3. 다 오른쪽으로 줄세워서 priorityQueue로도 풀 수 있겠다. 94번 문제 풀이에서 사용했던 Morris Traversal를 이용해서이다.

직접 푼 풀이

소요시간: 7분(09:40 ~ 09:47)

#1. 순회해서 다 저장하고 priorityQueue로 해결
class Solution {
    public int kthSmallest(TreeNode root, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>((a,b) -> b-a);


        doKthSmallest(pq, root, k);

        return pq.poll();
    }

    private void doKthSmallest(PriorityQueue pq, TreeNode root, int k) {
        if (root == null) {
            return;
        }
        pq.add(root.val);
        if(pq.size() > k) pq.poll();

        doKthSmallest(pq, root.left, k);
        doKthSmallest(pq, root.right, k);
    }
}

#2. 다 오른쪽으로 줄세워서 priorityQueue: Morris Traversal
class Solution {
    public int kthSmallest(TreeNode root, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>((a,b) -> b-a);

        while(root != null) { 
            if (root.left != null) {
                TreeNode temp = root;
                root = root.left;
                temp.left = null;

                TreeNode next = root;
                while(next.right != null) {
                    next = next.right;
                }
                next.right = temp;
            } else {
                pq.add(root.val);
                if (pq.size() >k) pq.poll();
                root = root.right;
            }
        }

        return pq.poll();
    }
}

느낀점

1. 아.. bst는 이미 정렬되어 있구나. 그걸 이용하면 더 빨리 풀 수 있구나.
2. bst특성을 파악하고 recursive하게 iterative하게 풀어봤다.
3. bst가 문제라면 그 특성을 이해하자. 그래도 역시 k-th는 priorityQueue면 한방이다.

솔루션 공부 후 추가로 푼 풀이

#bst recursive
class Solution {
    public int kthSmallest(TreeNode root, int k) {
        List<Integer> result = new ArrayList<>();

        inorder(root, result, k);

        return result.get(k-1);
    }

    private void inorder(TreeNode root, List<Integer> result, int k) {
        if (root == null || result.size() == k) {
            return;
        }

        inorder(root.left, result, k);
        result.add(root.val);
        inorder(root.right, result, k);   
    }
}

#bst iterative
class Solution {
    public int kthSmallest(TreeNode root, int k) {

        List<Integer> result = new ArrayList<>();
        LinkedList<TreeNode> stack = new LinkedList<>();
        while(true) {
            while(root != null) {
                stack.push(root);
                root = root.left;
            }

            root = stack.pop();
            result.add(root.val);
            if (result.size() == k) {
                break;
            }
            root = root.right;
        }

        return result.get(k-1);
    }
}

누적되는 알고리즘 접근 설명서

2021/01/09 - [알고리즘 풀이] - .leetcode(알고리즘 문제풀이 접근)