来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/kth-smallest-element-in-a-bst 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。

解答

根据二叉搜索树生成升序数组，返回第 k 大的元素

  1. /**
  2.  * Definition for a binary tree node.
  3.  * function TreeNode(val, left, right) {
  4.  *     this.val = (val===undefined ? 0 : val)
  5.  *     this.left = (left===undefined ? null : left)
  6.  *     this.right = (right===undefined ? null : right)
  7.  * }
  8.  */
  9. /**
  10.  * @param {TreeNode} root
  11.  * @param {number} k
  12.  * @return {number}
  13. */
  14. function treeToArr (root, nodes, k) {
  15.     if (!root) return null;
  16.     if (nodes.length <= k) {
  17.         treeToArr(root.left, nodes, k);
  18.         nodes.push(root.val);
  19.         treeToArr(root.right, nodes, k);   
  20.     }
  21. }
  22. var kthSmallest = function(root, k) {
  23.     const nodes = [];
  24.     treeToArr(root, nodes, k - 1);
  25.     return nodes[k - 1];
  26. };

优化

使用迭代解决，迭代的重点：

  1. 有左子节点，就一直往左子节点走，把节点缓存到数组中
  2. 无左子节点了，从数组 pop 最后一个节点出来处理
  3. 处理完成之后，把当前节点赋值为右子节点
    /**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
*     this.val = (val===undefined ? 0 : val)
*     this.left = (left===undefined ? null : left)
*     this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @param {number} k
* @return {number}
*/
var kthSmallest = function(root, k) {
 const stack = [];
 while (root || stack.length) {
     while (root !== null) {
         stack.push(root);
         root = root.left;
     }
     root = stack.pop();
     --k;
     if (k === 0) {
         return root.val;
     }
     root = root.right;
 }
};