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小的结点
思路：
只要明白BST树的原理，只要中序遍历一遍BST树即可。求第K小的，只需遍历前K个结点就OK。
C++：
/**
* 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 ret, cnt, _k; void rec(TreeNode *root)
{
if(root->left == && root->right == )
{
cnt++;
if(cnt == _k)
ret = root->val;
return ;
} if(root->left != )
rec(root->left); cnt++;
if(cnt == _k){
ret = root->val;
return ;
} if(root->right != )
rec(root->right);
} int kthSmallest(TreeNode* root, int k) {
if(root == )
return ; _k = k; cnt = ret = ; rec(root); return ret;
}
};
Python：
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None class Solution:
# @param {TreeNode} root
# @param {integer} k
# @return {integer} def __init__(self):
self.cnt = 0
self.ret = 0 def rec(self, root, k):
if root.left is None and root.right is None:
self.cnt = self.cnt + 1
if self.cnt == k:
self.ret = root.val
return if root.left is not None:
self.rec(root.left, k) self.cnt = self.cnt + 1
if self.cnt == k:
self.ret = root.val
return if root.right is not None:
self.rec(root.right, k) def kthSmallest(self, root, k):
if root is None:
return 0 self.rec(root, k) return self.ret