剑指Offer[54]-二叉搜索树的第k大节点

题目

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

示例：

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

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

python代码

class Solution:
    def kthLargest(self, root: TreeNode, k: int) -> int:
        def inorder(node):
            if not node:
                return
            inorder(node.left)
            self.outlist.append(node.val)
            inorder(node.right)

        self.outlist = []
        inorder(root)
        return self.outlist[-k]

其实，如果知道了“二叉树搜索树的中序遍历就是一个递增数组”，那这道题就很好解决，上述的代码也是先获得二叉树搜索树的中序遍历，直接取低k大个值即可。

思考

为什么搜索二叉树的中序遍历是一个递增数组？思考中序遍历的顺序：左-中-右，而搜索二叉树中值大小的关系是右>中>左，所以中序遍历正好是按照从小到大的顺序遍历。