LeetCode-Solutions-in-Cpp17

Solutions to high-frequency interview questions of LeetCode in C++17, taking into account both efficiency and comprehensibility.

---

Project maintained by downdemo Hosted on GitHub Pages — Theme by mattgraham

• 二叉搜索树的中序遍历是升序序列，利用此特点，中序遍历到第 k + 1 个数即可

class Solution {
 public:
  int kthSmallest(TreeNode* root, int k) {
    int res = 0;
    dfs(root, res, k);
    return res;
  }

  void dfs(TreeNode* root, int& res, int& k) {
    if (!root || k == -1) {
      return;
    }
    dfs(root->left, res, k);
    --k;
    if (!k) {
      k = -1;
      res = root->val;
      return;
    }
    dfs(root->right, res, k);
  }
};

• 非递归中序遍历

class Solution {
 public:
  int kthSmallest(TreeNode* root, int k) {
    if (!root) {
      return 0;
    }
    int res = 0;
    stack<TreeNode*> s;
    TreeNode* t = root;
    while (t || !empty(s)) {
      while (t) {
        s.emplace(t);
        t = t->left;
      }
      t = s.top();
      s.pop();
      if (k-- == 1) {
        res = t->val;
        break;
      }
      t = t->right;
    }
    return res;
  }
};