面试题54. 二叉搜索树的第k大节点

二叉搜索树的第k大节点

题目描述

给定一棵二叉搜索树，请找出其中第k大的节点。

示例：

提示：
1 ≤ k ≤ 二叉搜索树元素个数

转载来源：力扣（LeetCode）

题目分析

重点：二叉搜索树的中序遍历是从小到大的序列
上面的中序遍历是默认的先左后右的中序遍历，这道题将顺序调转一下，先有后左，得到的是由大到小的序列，这里用一个全局变量记录一下当前遍历了多少个数（完全执行完第一步的右遍历的节点才当做“遍历了的节点”），这样就很容易获得第K大的数了

class Solution {
    var num = 0
    fun kthLargest(root: TreeNode?, k: Int): Int {
        return postOrder(root,k)!!
    }
   fun postOrder(root: TreeNode?, k:Int):Int?{
        if(root == null)
            return null
//        先遍历比这个数大的
        val v1 = postOrder(root.right,k)
        if(v1 != null)
            return v1
//        遍历这个数
        num++
        if(num == k)
            return root.`val`
//        遍历比这个数小的
        val v2 = postOrder(root.left,k)
        if (v2 != null)
            return v2
        return null
    }
}

代码文件