题目描述
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);
- }
- };
来源: http://www.bubuko.com/infodetail-3105248.html