Leetcode -- the kth largest node of the binary search tree (traversal by means of middle order)

Title Description

Their thinking

First of all, we need to know what is a binary search tree , The characteristic of binary search tree is that the left child node of a node is smaller than the node , The right child node is larger than this node .

So what are the characteristics of the middle order traversal of binary search trees ？

Binary search tree : [3,1,4,null,2]
Middle order traversal result ：[1,2,3,4] The first 1 The big element is res.length - 1(k)： Subscript to be 3

Binary search tree ：[5,3,6,2,4,null,null,1]
Middle order traversal result ：[1,2,3,4,5,6] The first 3 The big element is res.length - 3(k)： Subscript to be 4

From the above example, we can see that , To find the second of a binary search tree K Big node , A binary search tree can be traversed in middle order , Then subtract the length of the traversal result array K That is the first. K Subscript corresponding to a large node .

1. If the incoming node is empty , Then return to null.

if (!root) return null;

2. Define result array

const res = [];

3. Do middle order traversal

const midOrder = (root) => {
    
    if (!root) return null;
    midOrder(root.left);
    res.push(root.val);
    midOrder(root.right);
    }
midOrder(root);

4. Return to binary search tree No K Subscript corresponding to a large node

return res[res.length - k];

AC Code

var kthLargest = function(root, k) {
    
    if (!root) return null;
    const res = [];
    const midOrder = (root) => {
    
    if (!root) return null;
    midOrder(root.left);
    res.push(root.val);
    midOrder(root.right);
    }
    midOrder(root);
    return res[res.length - k];
};

reflection

The second of binary search tree K Large nodes are a good topic , I originally wanted to traverse the binary search tree directly , And then sort it , Then go back to K Big nodes , But this obviously does not take advantage of the characteristics of binary search tree , In particular, it does not use the binary search tree to traverse the middle order , As long as we know the characteristics of middle order traversal of binary search tree , It can be easily solved .