当前位置 博文首页 > 数据结构和算法：LeetCode 230. 二叉搜索树中第K小的元素
截止到目前我已经写了 500多道算法题，其中部分已经整理成了pdf文档，目前总共有1000多页（并且还会不断的增加），大家可以免费下载
下载链接：https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ
提取码：6666
373，数据结构-6,树
488，二叉树的Morris中序和前序遍历
我们随便挑一个，比如二叉树中序遍历的递归写法如下
public void inOrderTraversal(TreeNode node) {
if (node == null)
return;
inOrderTraversal(node.left);
System.out.println(node.val);
inOrderTraversal(node.right);
}
我们来对他进行修改一下，就是这题的答案了
int target = -1;
int count;
public int kthSmallest(TreeNode root, int k) {
count = k;
inOrderTraversal(root);
return target;
}
public void inOrderTraversal(TreeNode node) {
if (node == null)
return;
//访问左子节点
inOrderTraversal(node.left);
//访问当前节点，如果访问到第k个就把target赋值
if (--count == 0) {
target = node.val;
return;
}
//访问右子节点
inOrderTraversal(node.right);
}
public int kthSmallest(TreeNode root, int k) {
//先统计左子节点的个数
int leftCount = countNodes(root.left);
if (leftCount >= k) {
//如果左子节点的个数大于等于k，说明我们要找的元素就在左子节点中，
//直接在左子节点中查找即可
return kthSmallest(root.left, k);
} else if (leftCount + 1 == k) {
//如果左子节点的个数加当前节点（1）正好等于k，说明根节点
//就是要找到元素
return root.val;
} else {
//否则要找的元素在右子节点中，到右子节点中查找
return kthSmallest(root.right, k - 1 - leftCount);
}
}
//统计节点个数
public int countNodes(TreeNode n) {
if (n == null)
return 0;
return 1 + countNodes(n.left) + countNodes(n.right);
}
