分类导航

PHP 发布时间：2022-04-04 发布网站：大佬教程 code.js-code.com

大佬教程收集整理的这篇文章主要介绍了剑指 Offer 53. 三叉搜索树的第b大节点，大佬教程大佬觉得挺不错的，现在分享给大家，也给大家做个参考。

题目介绍

描述：

给定一棵二叉搜索树，请找出其中第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 ≤ 二叉搜索树元素个数

解题思路：

二叉树解题策略

一递归二队列 + 迭代（层次遍历）三栈 + 迭代（非递归遍历）四其它

三种基本的遍历方式，都可以用递归来实现。写递归算法的时候，需要注意递归退出条件以及递归操作的表达。

二叉树的中序遍历是一个递增序列，所以中序遍历即可

自己的解法实现

def kthLargest(self, root, k):
        if not root: return 0
        self.res = []
        def Helper(nodE):
            if not node: return
            Helper(node.left)
            self.res.append(node.val)
            Helper(node.right)
            return self.res
        Helper(root)
        return self.res[::][-k]

网上比较优秀的解法

解法一

二叉搜索树的中序遍历为递增序列。二叉搜索树的中序遍历倒序为递减序列。求 “二叉搜索树第 kk 大的节点” 可转化为求 “此树的中序遍历倒序的第 kk 个节点”。

为求第 kk 个节点，需要实现以下三项工作：

递归遍历时计数，统计当前节点的序号；
递归到第 kk 个节点时，应记录结果 resres ；
记录结果后，后续的遍历即失去意义，应提前终止（即返回）。

def kthLargest2(self, root, k):
        def dfs(nodE):
            if not node: return
            dfs(node.right)
            self.k -= 1
            if self.k == 0:
                self.res = node.val
            dfs(node.left)

        self.k = k
        dfs(root)
        return self.res

解法二

中序遍历是升序数组。返回升序数组的倒数第k个节点，其下标为-k。

def kthLargest3(self, root, k):
        def inorder(nodE):
            if not node: return []
            return inorder(node.left) + [node.val] + inorder(node.right)

        return inorder(root)[-k]

解法三

二叉搜索树中，第1大到第len(nums-1)/2大一定位于右子树中，换句话说，如果k值满足：

1≤ k ≤len(nums−1)/2 则只遍历右子树就能找到第k大元素；

如果k值满足 k > len(nums-1) /2 才有必要去左子树中去查找；

def kthLargest4(self, root, k):
        self.count = k
        self.res = 0
        self.found = false    # 已经找到为True

        def travel(nodE):
            if not node or self.found: return

            # 遍历右子树
            travel(node.right)

            self.count -= 1
            if self.count == 0:
                self.res += node.val
                self.found = True
                return
            # 如果k > (len(nums)-1)/2，遍历左子树
            if not self.found:    # 没有找到再去左子树
                travel(node.left)
        travel(root)
        return self.res

相关知识总结和思考

相关知识：

BFS：广度/宽度优先。其实就是从上到下，先把每一层遍历完之后再遍历一下一层。

可以使用Queue的数据结构。我们将root节点初始化进队列，通过消耗尾部，插入头部的方式来完成BFS。

二叉搜索树（BST）的特性：

若它的左子树不为空，则所有左子树上的值均小于其根节点的值
若它的右子树不为空，则所有右子树上的值均大于其根节点的值
它的左右子树也分别为二叉搜索树

递归与迭代的区别

递归：重复调用函数自身实现循环称为递归；迭代：利用变量的原值推出新值称为迭代，或者说迭代是函数内某段代码实现循环；

剑指 Offer 53. 三叉搜索树的第b大节点