LeetCodeDay48 —— 二叉搜索树中第K小的元素★☆

230. 二叉搜索树中第K小的元素

描述

• 给定一个二叉搜索树，编写一个函数kthSmallest来查找其中第 k 个最小的元素。

说明

• 你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。

示例

示例 1:
输入: root = [3,1,4,null,2], k = 1
输出: 1

示例 2:
输入: root = [5,3,6,2,4,null,null,1], k = 3
输出: 3

进阶

如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k
小的值，你将如何优化kthSmallest函数？(参考)

思路

1. 二叉搜索树的中序遍历是个有序数列，所以求第 k 小的元素就是求中序遍历中第 k 个元素。
2. 两种实现方法，一种利用栈来实现的非递归算法，一种是递归算法。
3. 非递归解法，利用栈，让代码跟着思路走
   1）找到左子树最下边的节点，沿途的节点保存到栈中
   2）访问这个节点
   3）访问这个节点的右子树(对于程序而且，这是一棵新的树)，继续前面1 ~ 2的过程
   4）从栈中取出一个节点访问(此时左子树肯定已将都访问完毕了)，访问其右子树。

class Solution_230_01 {
 public:
  int kthSmallest(TreeNode* root, int k) {
    if (!root) return -1;
    stack<TreeNode*> mStack;
    TreeNode* node = root;
    vector<int> ret;
    while (node || !mStack.empty()) {
      while (node) {
        mStack.push(node);
        node = node->left;
      }
      node = mStack.top();
      mStack.pop();
      if (--k == 0) return node->val;
      node = node->right;
    }
    return -1;
  }
};

class Solution_230_01 {
 public:
  int kthSmallest(TreeNode* root, int k) {
    if(!root) return -1;
    return inorderTraversal(root, k); 
  }
  int inorderTraversal(TreeNode* node, int& k){
    int ret = -1;
    if(--k == 0) ret = node->val;
    if(ret == -1 && node->left)  ret = inorderTraversal(node->left, k);
    if(ret == -1 && node->rihgt)  ret = inorderTraversal(node->right, k);
    return ret; 
  }
};