寒冷大侠

文章
5
资源
0
加入时间
3年12月3天

剑指offer:给定一棵二叉搜索树,请找出其中的第k小的结点。

题目给定一棵二叉搜索树,请找出其中的第k小的结点。思路递归:由于二叉搜索树的性质是左子节点小于根节点,右子节点又比根节点大,所以我们可以先递归到最左边的子节点,那么这个节点就是最小的节点。从此节点开始计数,刚好就是从大到小排列的了。用栈的方法中序遍历,可以利用栈来模拟递归遍历,首先根入栈,然后令根节点的左孩子不断入栈直到为空,弹出栈顶,令其右孩子入栈,重复以上操作,直到遍历结束或者访问第k个节点为止。代码:递归/*struct TreeNode { int val;