剑指offer-题63：二叉搜索树的第k个结点

客官°小女子只卖身不卖艺 2022-05-26 02:30 152阅读 0赞

## **题目描述** ##

给定一颗二叉搜索树，请找出其中的第k大的结点。例如， 5 / \\ 3 7 /\\ /\\ 2 4 6 8 中，按结点数值大小顺序第三个结点的值为4。

实验平台：[牛客网][Link 1]

--------------------

## **解决思路：** ##

![这里写图片描述][70]

java:

/*
    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
    
        public TreeNode(int val) {
            this.val = val;
        }
    }
    */
    public class Solution {
        int k = 0;
    
        TreeNode KthNode(TreeNode pRoot, int k) {
            if (pRoot == null || k == 0) {
                return null;
            }
            this.k = k;
            return getKthNode(pRoot);
        }
    
        TreeNode getKthNode(TreeNode pRoot) {
            TreeNode target = null;
            if (pRoot.left != null) {
                target = getKthNode(pRoot.left);
            }
            if (target == null) {
                if (k == 1) {
                    target = pRoot;
                } else {
                    k--;
                }
            }
            if (target == null && pRoot.right != null) {
                target = getKthNode(pRoot.right);
            }
            return target;
        }
    }

python:

略

[Link 1]: https://www.nowcoder.com/ta/coding-interviews?page=1
[70]: /images/20220526/8259422ab7bf4f78be82e976e8efa08b.png

发表评论取消回复

表情：

评论列表（有 0 条评论，152人围观）

还没有评论，来说两句吧...

相关阅读

相关剑指offer 二叉树的第k个结点

[剑指offer题型分类及各题的解题思路与代码（<---点我跳转 ^ - ^）][offer_---_ _ -] 1、题目描述给定一棵二叉搜索树，...

古城微笑少年丶/ 2024年04月17日 14:12/ 0 赞/ 59 阅读

相关【剑指Offer】54. 二叉查找树的第 K 个结点

[力扣][Link 1] [NowCoder][] 解题思路利用二叉查找树中序遍历有序的特点。 / Definition for a binary t

深碍√TFBOYSˉ_/ 2022年12月02日 04:27/ 0 赞/ 110 阅读

相关剑指offer（C++）——二叉搜索树的第k个结点

题目描述给定一颗二叉搜索树，请找出其中的第k大的结点。例如， ![Center][] 按结点数值大小顺序第三个结点的值为4。思路：根据二叉搜索树

系统管理员/ 2022年06月17日 06:20/ 0 赞/ 157 阅读

相关《剑指offer》刷题笔记（树）：二叉搜索树的第k个结点

《剑指offer》刷题笔记（树）：二叉搜索树的第k个结点 -------------------- 转载请注明作者和出处：[http://blog.csdn.ne

我会带着你远行/ 2022年06月03日 09:42/ 0 赞/ 159 阅读

相关剑指offer-题63：二叉搜索树的第k个结点

题目描述给定一颗二叉搜索树，请找出其中的第k大的结点。例如， 5 / \\ 3 7 /\\ /\\ 2 4 6 8 中，按结点数值大小顺序第三个结点的值为4。实验平

客官°小女子只卖身不卖艺/ 2022年05月26日 02:30/ 0 赞/ 153 阅读

相关剑指Offer-二叉搜索树的第k个结点

题目描述给定一棵二叉搜索树，请找出其中的第k小的结点。例如，（5，3，7，2，4，6，8）中，按结点数值大小顺序第三小结点的值为4。 > 何为二叉搜索树？树中每一个

淡淡的烟草味﹌/ 2022年04月25日 01:24/ 0 赞/ 186 阅读

相关【剑指Offer】62二叉搜索树的第k个结点

题目描述给定一棵二叉搜索树，请找出其中的第k小的结点。例如，（5，3，7，2，4，6，8）中，按结点数值大小顺序第三小结点的值为4。时间限制：1秒；空间限

Love The Way You Lie/ 2022年04月05日 05:14/ 0 赞/ 165 阅读

相关【剑指Offer】（树）二叉搜索树的第k个结点

题目链接：[https://www.nowcoder.com/practice/ef068f602dde4d28aab2b210e859150a?tpId=13&tqId=11

红太狼/ 2022年03月16日 01:14/ 0 赞/ 184 阅读

相关 63. 二叉搜索树的第k个结点《剑指Offer》(Java版)

题目描述 > 给定一棵二叉搜索树，请找出其中的第k小的结点。例如，（5，3，7，2，4，6，8）中，按结点数值大小顺序第三小结点的值为4。 /

太过爱你忘了你带给我的痛/ 2022年01月30日 14:13/ 0 赞/ 155 阅读

相关剑指offer：二叉搜索树的第k个结点

试题：给定一棵二叉搜索树，请找出其中的第k小的结点。例如，（5，3，7，2，4，6，8）中，按结点数值大小顺序第三小结点的值为4。代码：二叉搜索树具有左子

女爷i/ 2021年06月24日 16:10/ 0 赞/ 320 阅读