“This is the 29th day of my participation in the Gwen Challenge in November. See details of the event: The Last Gwen Challenge in 2021”

54. The KTH largest node in the binary search tree

The title

Given a binary search tree, find the KTH largest node.

 

Example 1:

Input: root = [3,1,4, NULL,2], k = 1 3 / \ 1 4\2 Output: 4Copy the code

Example 2:

Input: root = [5,3,6,2,4,null,null,1], k = 3 5 / \ 3 6 / \ 2 4/1 output: 4Copy the code

 

Limitations:

1 ≤ K ≤ Number of binary search tree elements

Answer key

Ask questions

  • What is a binary search tree?

Binary search tree

  • Binary search tree, if its left subtree is not empty, the value of all nodes in the left subtree is less than the value of its root, if its right subtree is not empty, the value of all nodes in the right subtree is greater than the value of its root.

Middle order traversal analysis

  • We can do this with a middle-order traversal of a binary tree.
  • Middle order traversal formula: left -> root -> right, combined with the above binary search tree properties
3 / \ 1 4\2Copy the code
  • You can get: 1234 from small to large arrayansAccording to what is givenkWe’re throughans[ans.length-k]And obtain the KTH big node

Order traversal pseudocode

  • defineansUsed to store the value of traversing the binary tree
  • definein_orderThe () method is used to sequentially traverse a binary tree in recursion
  • In the first place to judgerootWhether the value is null: YesnullIt goes straight back0
  • Otherwise, call the current node recursively firstleftAnd thenpushOf the current noderoot.valtoansArray, the last recursive call to the current noderight
  • When the recursive call is complete, passans[ans.length-k]You can get the KTH large node
  • Finally, the KTH node of the binary search tree is realized

Sequence traversal code implementation

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} k
 * @return {number}
 */
var kthLargest = function(root, k) {
    let ans = []
    in_order(root,ans)
    return ans[ans.length-k]
};

var in_order = function(root,ans){
    if(root == null) return 0
    in_order(root.left,ans)
    ans.push(root.val)
    in_order(root.right,ans)
    return
}
Copy the code

Compare the number of right subtree nodes with k analysis

  • defineansUsed to store the value of traversing the binary tree
  • definegetCountMethod is used to get the number of right nodes in a binary search tree
  • throughcnt_rNumber of right nodes andkValue contrast
  • ifcnt_rNumber of right nodes >= kValue indicates that the KTH largest node is called recursively from the right nodekthLargest(root.right,k)
  • ifcnt_rNumber of right nodes == kThe value indicates that the KTH largest node indicates the current noderootThat’s the KTH largest node
  • Otherwise, it means that the KTH node is in the left node, so the value of K needs to be reducedk-cnt_r-1And call it recursivelykthLargest(root.left,k-cnt_r-1)

Compare the number of right subtree nodes with k code implementation

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} k
 * @return {number}
 */
var kthLargest = function(root, k) {
    let cnt_r = getCount(root.right)
    if(k <= cnt_r) return kthLargest(root.right,k)
    if(k == cnt_r + 1) return root.val
    return kthLargest(root.left,k-cnt_r-1)
};

var getCount = function(root){
    if(root == null) return 0
    return getCount(root.left) + getCount(root.right) + 1
}
Copy the code