Day4 二叉搜索树的第k大节点【树】【易】

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

思路：

• 二叉搜索树的定义
  • 二叉搜索树，又称二叉排序树，分两种情况：
    ① 空树
    ② 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。
• 由二叉搜索树的特性可得：二叉搜索树的中序遍历是一个递增序列。
  • 中序遍历得到序列nums，长度为n，下标对应0~n-1。
  • 第1大的节点，为nums[n-1]
  • 第2大的节点，为nums[n-2]
  • 第n大的节点，为nums[0]
  • 推出，第k大的节点，为nums[n-k]

思路总结：
先对二叉搜索树进行中序遍历，存入数组nums。nums[n-k]对应的值即为 第k大的节点的val

存疑：
？题目要求节点，我们得到的是节点的val，还对了。
倒数第二行代码去掉".val",报错如下

代码：

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

class Solution:
    global nums#将数组nums设为全局变量（如果定义在中序遍历函数里，每进一次函数，nums之前的值都会丢失，又刷成空列表[]）
    nums=[]
    def kthLargest(self, root: TreeNode, k: int) -> int:
        self.inorder(root)
        n=len(nums)
        return nums[n-k]
    def inorder(self,root):
        if root:
            self.inorder(root.left)
            nums.append(root.val)
            self.inorder(root.right)

最后

以上就是现代钥匙为你收集整理的Day4 二叉搜索树的第k大节点【树】【易】的全部内容，希望文章能够帮你解决Day4 二叉搜索树的第k大节点【树】【易】所遇到的程序开发问题。

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