題目敘述

題目難度：Medium
題目敘述：給定一個 Binary Search Tree 的 root，以及一個整數 k ，回傳第 $k^{th}$ 小的節點值

解法

這題是刷題到目前下來解最快的一題，從打開題目到最後 Accept 大概花 15 分鐘，其中包含 5 分鐘在local端手動寫測試

一開始的想法

題目要求回傳第 K 個最小的節點值，所以想法很簡單，首先 BST 的由左至右的大小排序跟你對樹進行 In-Order Traversal 的順序會一致，因此當你進行 In-Order Traversal 第一個拜訪的節點就會是最小值，接著拜訪到的就是 BST 中第二小的節點，依序下去…。因此只要透過一個 counter 來計算現在是否第K個節點就好，如果找到就回傳節點值。

我的解法

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int count =0;
    int result;
    void dfs(TreeNode *current, int k){
        if(current==nullptr) return;
        dfs(current -> left, k);
        //node visiting
        count++;
        if(count==k){result=current->val;return}
        dfs(current -> right,k);

    }   
    int kthSmallest(TreeNode* root, int k){
        if(root==nullptr) return -1;
        dfs(root, k);
        return result;
    }
};