“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 array
ans
According to what is givenk
We’re throughans[ans.length-k]
And obtain the KTH big node
Order traversal pseudocode
- define
ans
Used to store the value of traversing the binary tree - define
in_order
The () method is used to sequentially traverse a binary tree in recursion - In the first place to judge
root
Whether the value is null: Yesnull
It goes straight back0
- Otherwise, call the current node recursively first
left
And thenpush
Of the current noderoot.val
toans
Array, the last recursive call to the current noderight
- When the recursive call is complete, pass
ans[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
- define
ans
Used to store the value of traversing the binary tree - define
getCount
Method is used to get the number of right nodes in a binary search tree - through
cnt_r
Number of right nodes andk
Value contrast - if
cnt_r
Number of right nodes>= k
Value indicates that the KTH largest node is called recursively from the right nodekthLargest(root.right,k)
- if
cnt_r
Number of right nodes== k
The value indicates that the KTH largest node indicates the current noderoot
That’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 reduced
k-cnt_r-1
And 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