给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。说明：你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。示例 1:输入: root = [3,1,4,null,2], k = 13/ \1 4\2输出: 1
解题思路
变量 cnt:统计已经按序遍历多少个节点了
变量 r： 记录 第 k 个最小元素的值
根据二叉搜索树中序遍历的性质，我们可以按二叉树节点大小访问二叉树，记录下第k个遍历的节点，就是我们需要找到的第 k 个最小元素
代码
/*** Definition for a binary tree node.* public class TreeNode {*int val;*TreeNode left;*TreeNode right;*TreeNode() {}*TreeNode(int val) { this.val = val; }*TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;*}* }*/class Solution {int r = -1;int cnt = 0;public int kthSmallest(TreeNode root, int k) {mid(root, k);return r;}public void mid(TreeNode root, int k) {if (root == null) return;mid(root.left, k);if (++cnt == k)r = root.val;mid(root.right, k);}}
