题目描述
给定一棵二叉搜索树，请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8） 中，按结点数值大小顺序第三小结点的值为4。
二叉搜索树的第K个节点
解题思路：
- 二叉搜索树的中序遍历为 递增序列 。
在这里插入图片描述
求解第k个节点相当于递增序列从左到右第k个节点：
- 递归遍历计数，统计当前节点序号count
- 递归统计计数到k时，满足题目要求，保存结果节点到全局变量中
- 递归结束，后续遍历为无意义遍历，停止遍历，返回结果
递归解析：
- 终止条件：节点为null时，直接返回
- 递归左子树
- 统计当前遍历过的节点
- 递归右子树
参考代码：
public class Solution {
private int count,k;
private TreeNode reslutNode;
TreeNode KthNode(TreeNode pRoot, int k) {
if (pRoot == null) return null;
this.k=k;
inOrder(pRoot);
return reslutNode;
}
private void inOrder(TreeNode pRoot){
inOrder(pRoot.left);
count++;
if (count == k){
reslutNode = pRoot;
return;
}
inOrder(pRoot.right);
}
}
参考文章：leetcode类似题目题解
类似题目：Leetcode_剑指Offer_面试题54. 二叉搜索树的第k大节点
本文由博客群发一文多发等运营工具平台 OpenWrite 发布
