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

• 二叉搜索树，即 BST（Binary Search Tree），空树是二叉搜索树，如果不为空，其左子树（若不为空）的节点值均小于根节点，右子树（若不为空）的节点值均大于根节点，其左子树和右子数也是二叉搜索树

    4
   / \
  2   6
 / \ / \
1  3 5  7

注意要求是左右子树的所有节点与根节点比较
而不只是左右节点与根节点比较，下面就不是二叉搜索树
    4
   / \
  2   6
 / \ / \
1  5 3  7

5 大于 4，3 小于 4，不符合条件

• 依此定义递归判断即可

class Solution {
 public:
  bool isValidBST(TreeNode* root) { return dfs(root, nullptr, nullptr); }

  bool dfs(TreeNode* root, TreeNode* l, TreeNode* r) {
    if (!root) {
      return true;
    }
    if (l && root->val <= l->val) {
      return false;
    }
    if (r && root->val >= r->val) {
      return false;
    }
    return dfs(root->left, l, root) && dfs(root->right, root, r);
  }
};

• 二叉搜索树的中序遍历结果将由小到大排序，也可以用此特点来判断

class Solution {
 public:
  bool isValidBST(TreeNode* root) {
    if (!root) {
      return true;
    }
    vector<int> v;
    inorderTraversal(root, v);
    return is_sorted(begin(v), end(v), less_equal<int>{});
  }

  void inorderTraversal(TreeNode* root, vector<int>& v) {
    if (!root) {
      return;
    }
    inorderTraversal(root->left, v);
    v.emplace_back(root->val);
    inorderTraversal(root->right, v);
  }
};

• 也可以不存储到数组中，而是在中序遍历过程中与前驱节点比较

class Solution {
 public:
  bool isValidBST(TreeNode* root) {
    if (!root) {
      return true;
    }
    if (!isValidBST(root->left)) {
      return false;
    }
    if (pre && pre->val >= root->val) {
      return false;
    }
    pre = root;
    if (!isValidBST(root->right)) {
      return false;
    }
    return true;
  }

 private:
  TreeNode* pre = nullptr;
};