给定一个二叉搜索树,编写一个函数kthSmallest
来查找其中第k个最小的元素。
说明:
你可以假设 k 总是有效的,1 ≤ k ≤ 二叉搜索树元素个数。
示例 1:
输入: root = [3,1,4,null,2], k = 13/ \1 4\2输出: 1
示例 2:
输入: root = [5,3,6,2,4,null,null,1], k = 35/ \3 6/ \2 4/1输出: 3
一个中序遍历的搜索,递归或者栈。
/*** Definition for a binary tree node.* struct TreeNode {*int val;*struct TreeNode *left;*struct TreeNode *right;* };*/void inorderSearch(struct TreeNode* root,int* count,int k,int* target){if(*count>k)return;if(root->left)inorderSearch(root->left,count,k,target);(*count)++;if(*count==k){*target=root->val;return ;}if(root->right)inorderSearch(root->right,count,k,target);}int kthSmallest(struct TreeNode* root, int k) {int target=0;int count=0;inorderSearch(root,&count,k,&target);return target;}