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

230. 二叉搜索树中第 K 小的元素 - 力扣（LeetCode）

class Solution {
  int Remaining, Value;
  bool FoundSmallest = false;

  void traverse(TreeNode *TN) {
    if (TN->left)
      traverse(TN->left);
    else
      FoundSmallest = true;

    if (Remaining == 0)
      return;

    Value = TN->val;
    if (FoundSmallest)
      --Remaining;

    if (TN->right)
      traverse(TN->right);
  }

public:
  int kthSmallest(TreeNode* root, int k) {
    Remaining = k;
    traverse(root);
    return Value;
  }
};

BST 的性质告诉我们它当中的最小元素一定是在中序遍历过程中第一个不存在左子树的节点。所以，可以以这个特性为基础设置 FoundSmallest 作为 flag，并且使用 Remaining 作为步数计数来实现查找第 K 小的目的。

此处注意，是什么序遍历，终止条件就应该写在什么位置。比如此处判断是否还有留余步数的终止条件应该正好写在对 Value 赋值之前，不能写在其它位置。

二刷

class Solution {
  int Kth, K;
  void Traverse(TreeNode *TN) {
    if (!TN)
      return;

    Traverse(TN->left);
    // You should put all inorder operations here. Mind those operations that
    // have side effects. Fixed point should be put BEFORE those operations.
    if (K-- < 1)
      return;
    Kth = TN->val;
    Traverse(TN->right);
  }
public:
  int kthSmallest(TreeNode* root, int k) {
    K = k;
    Traverse(root);
    return Kth;
  }
};

没什么好说的，但是记住不动点一定要放在有副作用的语句之前。

三刷

class Solution {
public:
  int kthSmallest(TreeNode* root, int k) {
    stack<TreeNode *> S;
    while (root || !S.empty()) {
      while (root) {
        S.push(root);
        root = root->left;
      }
      root = S.top();
      S.pop();

      if (--k == 0)
        return root->val;

      root = root->right;
    }
    unreachable();
  }
};

官解2和3是什么玩意，我操。

class Solution {
  int Remaining;
  int Result;
  void Traverse(TreeNode *TN) {
    if (!TN)
      return;

    Traverse(TN->left);
    if (--Remaining == 0)
      Result = TN->val;
    Traverse(TN->right);
  }
public:
  int kthSmallest(TreeNode* root, int k) {
    Remaining = k;
    Traverse(root);
    return Result;
  }
};

这还有个递归版。不过其实这个写得不如二刷版本，可以发现没有early return。