剑62—二叉搜索树的第k大的结点

题目描述

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

解题思想

按照中序遍历的顺序遍历一颗二叉搜索树，遍历序列的数值是递增排序的。则很容易找到第k大个数

/* public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */ public class Solution { int index = 0; //计数器 TreeNode KthNode(TreeNode root, int k) { if(root != null) //中序遍历寻找第k个 { //左 TreeNode node = KthNode(root.left,k); if(node != null) return node; index ++; //中 if(index == k) return root; //右 node = KthNode(root.right,k); if(node != null) return node; return node; } return null; } }