Topic describes

Given a binary search tree, find the KTH largest node. The sample1: Enter: root = [3.1.4.null.2], k = 1
   3
  / \
 1   4
  \
   2Output:4The sample2: Enter: root = [5.3.6.2.4.null.null.1], k = 3
       5
      / \
     3   6
    / \
   2   4
  /
 1Output:4
Copy the code

DFS+ order traversal

  1. Since the title is a binary search tree, we can consider that the middle order traversal of a binary search tree is an ordered sequence.
  2. And since we’re trying to find the KTH largest, we can do it in “right root left” order, just in reverse order.
  3. In order traversal, according to the number of orders recorded in K value, when K is 0, the middle-order value traversed is the node with the KTH largest value

The sample code

def kthLargest(self, root: TreeNode, k: int) - >int:
    def dfs(root) :
        if not root:
            return
        dfs(root.right) The right node is traversed in order

        if self.k == 0: # K judgment
            return

        self.k -= 1
        if self.k == 0:
            self.res = root.val
        dfs(root.left) The left node is traversed in order

    self.k = k
    self.res = 0
    dfs(root)
    return self.res
Copy the code