本篇文章为你整理了每日算法之二叉搜索树的第k个节点（找出一个二叉搜索树中第k小的级点）的详细内容，包含有二叉搜索树序列 找出一个二叉搜索树中第k小的级点 二叉搜索树是在n个元素 一颗二叉搜索树共有n个节点,最差时间复杂度 每日算法之二叉搜索树的第k个节点，希望能帮助你了解 每日算法之二叉搜索树的第k个节点。
算法实现
根据二叉搜索树的性质，左子树的元素都小于根节点，右子树的元素都大于根节点。因此它的中序遍历（左中右）序列正好是由小到大的次序，
因此我们可以尝试递归中序遍历，也就是从最小的一个节点开始，找到k个就是我们要找的目标。
具体做法：
step 1：设置全局变量count记录遍历了多少个节点，res记录第k个节点。
step 2：另写一函数进行递归中序遍历，当节点为空或者超过k时，结束递归，返回。
step 3：优先访问左子树，再访问根节点，访问时统计数字，等于k则找到。
step 4：最后访问右子树。
package mid.JZ54二叉搜索树的第k个节点;
import java.util.*;
class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
public class Solution {
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* @param proot TreeNode类
* @param k int整型
* @return int整型
public int KthNode(TreeNode proot, int k) {
midOrder(proot, k);
if (res != null) {
return res.val;
} else {
return -1;
public int KthNode2(TreeNode proot, int k) {
// write code here
if(proot == null k == 0) return -1;
List Integer res = new ArrayList ();
def(proot, res);
System.out.println(res.size());
System.out.println(k);
System.out.println(res.size()
if(res.size() k) return -1;
Collections.sort(res);
return res.get(k-1);
public void def(TreeNode proot, List Integer res) {
if (proot == null) return;
def(proot.left, res);
res.add(proot.val);
def(proot.right, res);
//记录返回的节点
private TreeNode res = null;
//记录中序遍历了多少个
private int count = 0;
public void midOrder(TreeNode root, int k) {
if (root == null count k) return;
midOrder(root.left, k);
count++;
if (count == k) {
res = root;
midOrder(root.right, k);
以上就是每日算法之二叉搜索树的第k个节点（找出一个二叉搜索树中第k小的级点）的详细内容，想要了解更多 每日算法之二叉搜索树的第k个节点的内容，请持续关注盛行IT软件开发工作室。
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。