230. The KTH smallest element in a binary search tree

The title

Given the root node of a binary search tree, root, and an integer k, design an algorithm to find the smallest element (counting from 1), k ****.

Example 1

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

Answer key

Search binary tree order traversal, the array is strictly increasing;

This is very important

So method 1

recursive

Recursively get the middle order traversal number group, return the k-1 number can be

var kthSmallest = function (root, k) {
  const array = [];
  helper(root);
  return array[k - 1];
  function helper(root) {
    if (root === null) return;
    if (array.length === k) return; helper(root.left); array.push(root.val); helper(root.right); }};Copy the code

Recursive optimization

Middle order traversal will put the data in the array, return the array k-1 bit of data, this step can be optimized, in the middle order traversal process record the enumeration of k-1 number, record, middle order traversal end, directly return

var kthSmallest = function (root, k) {
  let result = null
  function helper(node) {
    if(! node || result ! = =null) {
      return
    }
    helper(node.left)
    k--
    if (k === 0) {
      result = node.val
    }
    helper(node.right)
  }
  helper(root)
  return result
}
Copy the code