Leetcode.230.Kth Smallest Elemen

题目

给定一个BST，找出第k小的数。

Input: root = [3,1,4,null,2], k = 1
       3
      / \
     1   4
      \
        2
Output: 1
Input: root = [5,3,6,2,4,null,null,1], k = 3
           5
          / \
         3   6
        / \
       2   4
      /
     1
Output: 3

思路

递归。BST是左边小于中间小于右边。所以左边的左边的左边是最小的，倒数第二小是左边的左边的...的右边。所以每次取完左边后计算加1.

void kthSmallestHelper(TreeNode* root,int target,int &count,int &res) {
    if (!root) return;
    kthSmallestHelper(root->left,target,count,res);
    count++;
    if (count == target) {
        res = root->val;
        return;
    }
    kthSmallestHelper(root->right, target, count, res);
}

int kthSmallest(TreeNode* root, int k) {
    int res = 0, count = 0;
    kthSmallestHelper(root, k, count, res);
    return res;
}

总结

熟练掌握递归的迭代顺序。