一、題目

給定一顆二叉搜索樹，請找出其中的第k大的結點。例如， 5 / \ 3 7 /\ /\ 2 4 6 8 中，按結點數(shù)值大小順序第三個結點的值為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;//計數(shù)器 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 }

?

轉載于:https://www.cnblogs.com/fankongkong/p/7462149.html

總結

以上是生活随笔為你收集整理的60、二叉搜索树的第k个结点的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。