題目網址：https://leetcode.cn/problems/kth-smallest-element-in-a-bst/

題意：給一 BST 的 root 和一整數 k, 返回 BST 中第 k 小的元素（從 1 開始計數）。

Solution：

想法：利用 BFS（inorder）, 不斷取當前 node 的 left 直到 node->left 為 null, 由於 left child 是「後進先出」, 故要使用 stack。將這些 left 一個一個 pop 掉, 並將 k 減去 1

  • 若 k == 0, 代表當前 node 為第 k 小的數
  • 若 k > 0, 代表當前的數還太小, 故要嘗試其右子樹中的 node
class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        stack<TreeNode*> stk;
        stk.emplace(root);

        while (!stk.empty()) {
            // 不斷加入 left child, 直到 left child 為 null
            while (root) {
                stk.emplace(root);
                root = root->left;
            }

            // 取出最左邊的 node
            root = stk.top();
            stk.pop();
            --k; // 扣除 root 本身

            // k == 0, 代表當前 root 為第 k 小的
            if (k == 0) {
                break;
            }

            // 嘗試最左邊的 node 之 right subtree
            root = root->right;
        }
        return root->val;
    }
};
  • time：$O(n)$ ➔ worse case：skew tree, 其中 n 為 node 數
  • space：$O(n)$ ➔ 取決於 stack 長度, 最大長度為 n