题目描述

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.

Note: 
You may assume k is always valid, 1 ≤ k ≤ BST's total elements.

 

题目大意

给定一棵搜索二叉树，要求找到树结点中第k小的数字。

 

示例

E1

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

E2

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

 

解题思路

简单的中序遍历一遍，利用一个整数值记录访问了几个树结点即可，若访问了k个结点，记录返回该结点的整数值即可。

 

复杂度分析

时间复杂度：O(N)

空间复杂度：O(1)

 

代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        int res = 0, i = 0;
        // 中序遍历
        inorder(root, k, i, res);
        
        return res;
    }
    
    void inorder(TreeNode* node, int& k, int& i, int& res) {
        if(node == NULL)
            return;
        // 遍历左结点
        inorder(node->left, k, i, res);
        // 将访问的结点数加一，若以访问了k个结点，则记录该结点整数值为结果，并返回
        ++i;
        if(i == k) {
            res = node->val;
            return;
        }
        // 若还没有访问k个结点，则继续访问该结点的右结点
        inorder(node->right, k, i, res);
    }
};