首页
登录 | 注册

60、二叉搜索树的第k个结点

一、题目

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

二、解法

 1 package algorithm7;
 2 
 3 public class KthNode62 {
 4     public static void main(String[] args) {
 5         KthNode62 kth = new KthNode62();
 6         TreeNode t1 = new TreeNode(5);
 7         TreeNode t2 = new TreeNode(3);
 8         TreeNode t3 = new TreeNode(7);
 9         TreeNode t4 = new TreeNode(2);
10         TreeNode t5 = new TreeNode(4);
11         TreeNode t6 = new TreeNode(6);
12         TreeNode t7 = new TreeNode(8);
13         t1.left = t2;
14         t1.right = t3;
15         t2.left = t4;
16         t2.right = t5;
17         t3.left = t6;
18         t3.right = t7;
19         TreeNode t = kth.KthNode(t1,8);
20         System.out.println(t.val);
21     }
22     int index = 0;//计数器
23     //用中序遍历,左 根 右
24     public  TreeNode KthNode(TreeNode pRoot, int k)
25     {
26         if(pRoot != null){
27             TreeNode node = KthNode(pRoot.left,k);//
28             if(node != null)//表示找到了结点
29                 return node;
30             
31             index++;//
32             if(index == k)
33                 return pRoot;//找到了
34             
35             node = KthNode(pRoot.right,k);//
36             if(node != null)//表示找到了结点
37                 return node;
38         }
39         return null;//遍历完了 返回空 或者该结点为空
40     }
41 }

 


相关文章

  • asp.net core系列 60 Ocelot 构建服务认证示例
    一.概述 在Ocelot中,为了保护下游api资源,用户访问时需要进行认证鉴权,这需要在Ocelot 网关中添加认证服务.添加认证后,ReRoutes路由会进行身份验证,并使用Ocelot的基于声明的功能.在Startup.cs中注册认证服 ...
  • Spring入门(二):自动化装配bean
    Spring从两个角度来实现自动化装配: 组件扫描(component scanning):Spring会自动发现应用上下文中需要创建的bean. 自动装配(autowiring):Spring会自动满足bean之间的依赖. 为了更形象的解 ...
  • 使用 ASP.NET Core MVC 创建 Web API(二)
    使用 ASP.NET Core MVC 创建 Web API 使用 ASP.NET Core MVC 创建 Web API(一)     六.添加数据库上下文       数据库上下文是使用Entity Framework Core功能的主 ...
  • 详解linux进程间通信-消息队列
    前言:前面讨论了信号.管道的进程间通信方式,接下来将讨论消息队列. 一.系统V IPC 三种系统V IPC:消息队列.信号量以及共享内存(共享存储器)之间有很多相似之处. 每个内核中的 I P C结构(消息队列.信号量或共享存储段)都用一个 ...
  • 详解linux进程间通信-管道 popen函数 dup2函数
    前言:进程之间交换信息的唯一方法是经由f o r k或e x e c传送打开文件,或通过文件系统.本章将说明进程之间相互通信的其他技术—I P C(InterProcess Communication).今天将介绍半双工的管道. 一.匿名管 ...
  • 已迁移到我新博客,阅读体验更佳LDA && NCA: 降维与度量学习 代码实现放在我的github上:click me 一.Linear Discriminant Analysis(LDA) 1.1 Rationale    ...

2019 cecdns.com webmaster#cecdns.com
12 q. 0.076 s.
京ICP备10005923号