一、思路
二叉搜索樹的中序遍曆結果正好是從小到大排序好的，按照中序遍曆順序找第k個節點。
例如二叉搜索樹（20，10，30，2，11，24，38）中第三小結點的值爲11。
二、代碼
public Solution {
public static void main(String[] args) {
//構建二叉搜索樹
TreeNode root = new TreeNode(20);
root.left = new TreeNode(10);
root.right = new TreeNode(30);
root.left.left = new TreeNode(2);
root.left.right = new TreeNode(11);
root.right.left = new TreeNode(24);
root.right.right = new TreeNode(38);
Solution solution = new Solution();
//獲取第3小的節點
int k=3;
TreeNode node = solution.getKthNode(root,k);
if (null!=node) {
System.out.println("找到第"+k+"小的節點值爲："+node.value);
} else {
System.out.println("未找到第"+k+"小的節點");
}
}
//節點類
public static TreeNode {
int value;
TreeNode left;
TreeNode right;
TreeNode(int value) {
this.value = value;
}
}
//計數器
private int index = 0;
/**
* 獲取二叉搜索樹中第k個節點的對象
* @param root 二叉樹根節點
* @param k 要查的節點位置k
* @return 第k個節點對象，若存在則返回，不存在則返回null
*/
public TreeNode getKthNode(TreeNode root, int k){
if(root != null){
// 先查左子樹的第k小的節點
TreeNode node = getKthNode(root.left,k);
// 若左子樹中查到則直接返回
if(node != null) {
return node;
}
index ++;
//命中索引爲k的節點，直接返回
if(index == k) {
return root;
}
// 再查右子樹的第k小的節點
node = getKthNode(root.right,k);
// 若右子樹中查到則直接返回
if(node != null) {
return node;
}
}
return null;
}
}
微風不燥，陽光正好，你就像風一樣經過這裏，願你停留的片刻溫暖舒心。
我是程序員小迷（致力于C、C++、Java、Kotlin、Android、Shell、JavaScript、TypeScript、Python等編程技術的技巧經驗分享），若作品對您有幫助，請關注、分享、點贊、收藏、在看、喜歡，您的支持是我們爲您提供幫助的最大動力。
歡迎關注。助您在編程路上越走越好！
