题目描述
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
E2
解题思路
简单的中序遍历一遍，利用一个整数值记录访问了几个树结点即可，若访问了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); } };
LeetCode-230 Kth Smallest Element in a BST
原文：https://www.cnblogs.com/heyn1/p/11095773.html