230. Kth Smallest Element in a BST - Medium

前往題目

之前寫的文章

想法

• 用priority queue，取最小的前k個

思路

仔細觀察會發現這題的數字用inorder的方式traverse剛好會排成ascending的樣子

簡單來說就是，往左邊走就對了，沒有的話就pop，最後才走右邊

1. 借助stack的力量
2. 只要有左邊的node就push到stack，然後前往left node
3. 如果沒有左邊了就pop，然後前往right node
4. 沒有right node繼續pop

Code

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

        // Start inorder traverse
        while (currNode != null || !stack.isEmpty()) {
            // inorder
            while (currNode != null) {
                stack.push(currNode);
                currNode = currNode.left;
            }

            // No more left, begin popping
            currNode = stack.pop();
            // Add count
            n++;

            // Reached kth smallest element
            if (n == k) return currNode.val;
            // No more left, so start looking for the right
            currNode = currNode.right;
        }
        return k;
    }
}