题目
给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。
说明：
你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数
示例
输入: root = [3,1,4,null,2], k = 1 3 / 1 4 2 输出: 1
题解
参考Cyc大佬博客实现
本题可以分别利用中序遍历法和递归法进行求解。中序遍历法需要利用变量来记录好中间状态。
中序遍历法：
class Solution { private int value = 0; private int cnt = 0; public int kthSmallest(TreeNode root, int k) { inOrder(root, k); return value; } private void inOrder(TreeNode root, int k){ if(root == null){ return ; } inOrder(root.left, k); cnt++; if(cnt == k){ value = root.val; return ; } inOrder(root.right, k); } }
递归法
class Solution { /* 查找左子树节点个数N，当N+1==k时，则返回查找节点； 如果N+1 > k，则继续在左子树中查找，k值不变 否则的话在右子树中查找，此时k应减去原左子树节点个数与根节点之和，即为k-N-1 */ public int kthSmallest(TreeNode root, int k) { int N = totalChild(root.left); if(N == k - 1){ return root.val; } if(N < k - 1){ return kthSmallest(root.right, k - N - 1); } return kthSmallest(root.left, k); } private int totalChild(TreeNode root){ if(root == null){ return 0; } return totalChild(root.left) + totalChild(root.right) + 1; } }
原文：https://www.cnblogs.com/jianglinliu/p/11802445.html