《剑指offer》刷题系列——（二十六） 二叉搜索树的第k大节点

题目

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

思路

二叉搜索树，也叫二叉排序树、二叉查找树，它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉搜索树。

要找出树所有节点中的第K大值，最好的方法是能将树中所有节点进行排序，然后就很容易找到第K大的数。

根据二叉搜索树的特点，如果对树进行中序遍历，则能得到所有节点的递增序列，中序遍历的过程是，先访问左子树，然后访问根节点，最后访问右子树。
如果能在中序遍历的基础上稍微修改一下，先访问右子树，然后访问根节点，最后访问左子树，则能得到所有节点的递减序列。这样递减序列的第K个数就是我们要找的值。

代码

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def kthLargest(self, root: TreeNode, k: int) -> int:
        if not root:
            return None
        res = []
        self.dfs(root,res)
        return res[k-1]
    
    def dfs(self,root,res):
        if not root:
            return 
        self.dfs(root.right,res)
        res.append(root.val)
        self.dfs(root.left,res)

复杂度

时间复杂度 O(N) ： 当树退化为链表时（全部为右子节点），递归深度都为 N ，占用 O(N) 时间。
空间复杂度 O(N)： 使用了 O(N) 大小的列表用来保存所有节点的递减序列。

最后

以上就是自然可乐为你收集整理的《剑指offer》刷题系列——（二十六） 二叉搜索树的第k大节点的全部内容，希望文章能够帮你解决《剑指offer》刷题系列——（二十六） 二叉搜索树的第k大节点所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。