😋 分治
/**
* 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 {
public int kthSmallest(TreeNode root, int k)
{
int n = nodeCount(root.left);//计算当前树的左子树的结点数
if (n + 1 == k)// 说明根节点就是第 k 小的数
return root.val;
else if (n + 1 < k)// 说明第 k 小的数在当前树的 右子树的第（k-n-1)小处
return kthSmallest(root.right, k - n - 1);
else// 说明第 k 小的数在当前树的 左子树的 第（k)小处
return kthSmallest(root.left, k);
}
/**
* @param root 当前树的根节点
* @return 当前树的总结点数（包含根节点）
*/
int nodeCount(TreeNode root)
{
if (root == null)
return 0;
return 1 + nodeCount(root.left) + nodeCount(root.right);
}
}
😋 递归中序遍历
/**
* 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 num = 0;
int res;
public int kthSmallest(TreeNode root, int k) {
inorderTraversal(root, k);
return res;
}
private void inorderTraversal(TreeNode node, int k) {
if (node == null || num > k) {
return;
}
inorderTraversal(node.left, k);
num++;
if (num == k) {
res = node.val;
return;
}
inorderTraversal(node.right, k);
}
}
