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

题目描述

https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof
给定一棵二叉搜索树，请找出其中第k大的节点。

示例 1:

输入: root = [3,1,4,null,2], k = 1

   3
  / \
 1   4
  \
   2

输出: 4
示例 2:

输入: root = [5,3,6,2,4,null,null,1], k = 3
       5
      / \
     3   6
    / \
   2   4
  /
 1

输出: 4

限制：

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

解题思路

1.中序遍历
二叉搜索树使用中序遍历可以得到有序数组，取第k大的值输出。
2.逆中序遍历
使用RNL方式遍历，遍历到的第k个数就是第k大的值。

解题代码

中序遍历：

class Solution:
    def kthLargest(self, root: TreeNode, k: int) -> int:
        arr = []
        # 中序遍历
        def InOrder(node: TreeNode):
            if node is None:
                return
            InOrder(node.left)
            arr.append(node.val)
            InOrder(node.right)
        InOrder(root)
        return arr[len(arr) - k]

逆中序遍历：

class Solution:
    def kthLargest(self, root: TreeNode, k: int) -> int:
        self.i = 0
        self.result = 0
        # 中序遍历
        def ReverseInOrder(node: TreeNode):
            if node is None:
                return
            ReverseInOrder(node.right)
            self.i += 1
            if self.i == k:
                self.result = node.val
            ReverseInOrder(node.left)
        ReverseInOrder(root)
        return self.result

执行结果

中序遍历：64ms 18.9MB
逆中序遍历：68ms 18.5MB