【题54】二叉搜索树的第k大节点

朴灿烈づ我的快乐病毒、 2022-03-01 05:12 142阅读 0赞

【题目】  
给定一棵二叉搜索树，请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8） 中，按结点数值大小顺序第三小结点的值为4。  
【思路】  
考察树的中序排列  
【实现】

/*
    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
    
        public TreeNode(int val) {
            this.val = val;
    
        }
    
    }
    */
    import java.util.Stack;
    public class Solution {
        TreeNode KthNode(TreeNode pRoot, int k)
        {
            if(pRoot == null || k==0) return null;
            int count = 0;
            Stack<TreeNode> stack = new Stack<TreeNode>();
            TreeNode node = pRoot;
            do{
                if(node != null){
                    stack.push(node);
                    node = node.left;
                }else{
                    node = stack.pop();
                    count ++;
                    if(count == k) return node;
                    node = node.right;
                }
            }while(node != null||!stack.isEmpty());
            return null;
        }
    }

参考：  
1.《剑指offer》

发表评论取消回复

表情：

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

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

相关阅读

相关【剑指 Offer 54. 二叉搜索树的第k大节点】

package com.example.demomain.demoleetcode.easy; import java.util.ArrayList;

男娘i/ 2023年09月26日 17:04/ 0 赞/ 77 阅读

相关剑指offer | 54. 二叉搜索树的第k大节点

题目内容： > 给定一棵二叉搜索树，请找出其中第k大的节点。示例 1: 输入: root = [3,1,4,null,2], k = 1 3

太过爱你忘了你带给我的痛/ 2022年12月28日 00:48/ 0 赞/ 105 阅读

相关剑指 Offer 54. 二叉搜索树的第k大节点

题目给定一棵二叉搜索树，请找出其中第k大的节点。示例 1: ![在这里插入图片描述][20201105162840386.png_pic_center] 示例

迈不过友情╰/ 2022年12月19日 06:06/ 0 赞/ 106 阅读

相关二叉搜索树的第 k 大节点

二叉搜索树的第 k 大节点 1、参考资料 https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-di-kda

Myth丶恋晨/ 2022年12月05日 10:21/ 0 赞/ 120 阅读

相关 2021-03-11 | 剑指 Offer 54. 二叉搜索树的第k大节点

1. 题目描述给定一棵二叉搜索树，请找出其中第k大的节点。示例 1: 输入: root = [3,1,4,null,2], k = 1 3

淩亂°似流年/ 2022年11月12日 01:49/ 0 赞/ 91 阅读

相关剑指 Offer 54. 二叉搜索树的第k大节点

题目重述给定一棵二叉搜索树，请找出其中第k大的节点。示例 1: 输入: root = [3,1,4,null,2], k = 1 3

拼搏现实的明天。/ 2022年09月10日 01:15/ 0 赞/ 98 阅读

相关【剑指offer】面试题54：二叉搜索树的第k大节点

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

港控/mmm°/ 2022年06月11日 06:49/ 0 赞/ 91 阅读

相关二叉搜索树的第k个结点

![这里写图片描述][70] import java.util.; class TreeNode { int val = 0;

梦里梦外;/ 2022年05月24日 10:35/ 0 赞/ 152 阅读

相关【题54】二叉搜索树的第k大节点

【题目】给定一棵二叉搜索树，请找出其中的第k小的结点。例如，（5，3，7，2，4，6，8）中，按结点数值大小顺序第三小结点的值为4。【思路】考察树的中序排

朴灿烈づ我的快乐病毒、/ 2022年03月01日 05:12/ 0 赞/ 143 阅读

相关剑指Offer 54 二叉搜索树的第k大节点

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

Dear 丶/ 2021年12月19日 04:19/ 0 赞/ 160 阅读