二叉查找树：

  • 又叫（Binary Search Tree） 二叉搜索树
  • 特点：支持动态数据集合的快速插入、删除、查找操作。
  • 定义：
    • 任意节点的左子树中的键值都 小于 此节点的键值。
    • 任意节点的右子树中的键值都 大于 此节点的键值。
    • 任意节点的左子树和右子树都是二叉搜索树。
      1. // 判断是否是二叉查找树？
      2. bool IsBST(TreeNode* node, int minVal, int maxVal)
      3. {
      4. if (node == nullptr) {
      5.    return true;
      6. }
      7. if (node->val <= minVal || node->val >= maxVal) {
      8.    return false;
      9. }
      10. if (IsBST(node->left, minVal, node->val) == false) {
      11.    return false;
      12. }
      13. if (IsBST(node->right, node->val, maxVal) == false) {
      14.    return false;
      15. }
      16. return true;
      17. }
      18. IsBST(node, INT_MIN, INT_MAX); // 先判读是不是BST, 初始值很巧妙

      多叉树

      构造：使用map , （key, val）, key代表根节点，val代表子节点。val可以使用vector来记录。
      多叉树的遍历: DFS
      1. void dfs(vector<string>& names, vector<string>& ans)
      2. {
      3. if (names.size() == 0) {
      4.    return;
      5. }
      6. for (int i = 0; i < names.size(); i++) {
      7.    ans.push_back(names[i]);
      8.    dfs(mp[names[i]], ans);
      9. }
      10. return;
      11. }