剑指offer----二叉搜索树的第K个节点----java实现

分手后的思念是犯贱 2022-09-23 08:51 114阅读 0赞

思路：

根据二叉搜索树的特点来解决，非空二叉搜索树是左子树上的所有节点比根节点小，右子树上的所有节点比根节点大，其左右子树同样遵循这个规则。

所以二叉搜索树的中序遍历结果，就是一个按照从大到小的顺序排序的序列，访问第K个节点时就终止程序即可。

TreeNode KthNode(TreeNode pRoot, int k)
    	    {
    	        if(pRoot == null || k <= 0)
    	            return null;
    	        TreeNode current = pRoot;
    	        TreeNode kNode = null;//用来保存第K个节点
    	        int count = 0;
    	        LinkedList<TreeNode> stack = new LinkedList<TreeNode>();
    	        //中序遍历二叉搜索树
    	        while(!stack.isEmpty() || current != null)
    	       {
    	          while(current!=null)
    	         {
    	        	stack.push(current);
    	        	current = current.left;
    	         }
    	          if(!stack.isEmpty())
    	          {
    	        	  current = stack.pop();//每出栈一个节点让count++;对比count和K的值，第k个节点时跳出循环返回节点，
    	        	  count++;
    	        	  if(count == k)
    	        	  {
    	        		  kNode = current;
    	        		  break;
    	        	  }
    	        	  current = current.right;
    	          }
    	       }
    	        return kNode;
    	    }

发表评论取消回复

表情：

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

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

相关阅读

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

> 难度等级：容易 > 上一篇算法： > > [226. 翻转二叉树【58】][226. _58] > 力扣此题地址： > > [剑指 Offer 54. 二叉搜索树的

阳光穿透心脏的1/2处/ 2023年09月27日 18:17/ 0 赞/ 62 阅读

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

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

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

相关（Java 剑指 offer）二叉搜索树的第 k 个节点

文章目录一、题目解析二、代码三、总结一、题目解析给定一棵二叉搜索树，请找出其中的第 k 小的结点。例如，（5，

桃扇骨/ 2022年12月11日 15:09/ 0 赞/ 108 阅读

相关剑指offer----二叉搜索树的第K个节点----java实现

思路：根据二叉搜索树的特点来解决，非空二叉搜索树是左子树上的所有节点比根节点小，右子树上的所有节点比根节点大，其左右子树同样遵循这个规则。所以二叉搜索树的中序遍历结果，

分手后的思念是犯贱/ 2022年09月23日 08:51/ 0 赞/ 115 阅读

相关剑指offer_二叉搜索树的第k个节点

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

谁借莪１个温暖的怀抱￠/ 2022年06月09日 06:56/ 0 赞/ 129 阅读

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

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

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

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

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

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

相关剑指offer: 二叉搜索树的第K个节点

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

青旅半醒/ 2022年02月25日 15:48/ 0 赞/ 172 阅读

相关剑指offer66 ：二叉搜索树的第k个节点（java）

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

水深无声/ 2021年11月05日 00:31/ 0 赞/ 187 阅读

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

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

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