怎样应对IT面试与笔试-（五）

二叉搜索树

二叉树中的结点按照一定规则排序就变成了一颗二叉搜索树

• 的定义：
• 它或者是一棵空树，或者是具有下列性质的二叉树:
  (1) 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
  (2) 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
  (3) 它的左、右子树也分别为二叉排序树

• TIPS 有一点需要注意的是：
• 左子树中所有点都要小于根结点，右子树中所有点都要大于根结点。
• 下图中图a不是一个有效的二叉搜索树，因为结点6位于右子树，但小于根结点10,
  图b是一个有效的二叉搜索树

给一个二叉树，判断这个二叉树是否是有效的二叉搜索树。

1.举例子-画图-解题思路

2. 写核心逻辑代码

先看标准的错误代码：

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        if(!root)
            return true;
        
        return traversal(root);
    }
    bool traversal(TreeNode* root)
    {
        //递归的返回条件
        if(!root)
            return true;
         //左结点存在时候判断左结点值小于root值
        if(root->left && root->left->val >= root->val)
            return false;
        //右结点存在时候判断右结点值大于root值
        if(root->right && root->right->val <= root->val)
            return false;
        
       //递归检查左右结点            
        return traversal(root->left) && traversal(root->right);
    }
};

• 上述代码如果执行上图（BST）图a的case，会返回true，因为6只与15做了比较，没有比较6与10的大小

看来下面精简的正确算法

class Solution {
public:
    bool isValidBST(TreeNode *root) {
        //在这里LONG_MIN理解为极小值，LONG_MAX理解为极大值
        return isValidBST(root, LONG_MIN, LONG_MAX);
    }
    bool isValidBST(TreeNode *root, long mn, long mx) {
        if (!root) return true;
        if(root->val < mx && root->val > mn)
              return isValidBST(root->left, mn, root->val) && isValidBST(root->right, root->val, mx);
        else 
            return false;
    }
};

我们还是用图a的例子来解释下上面的代码：
（1）初始函数：isValidBST（10，LONG_MIN, LONG_MAX）
（2）先递归遍历左子树：isValidBST（5，LONG_MIN，10），5<10（保证了左结点小于根结点） && 5 > LONG_MIN，后面的判断结点为空的过程我们略去，不再描述。
（3）然后开始遍历右子树isValidBST（15，10，LONG_MAX），15 <LONG_MAX && 15 >10（保证了右结点大于根结点），继续执行isValidBST（6，10，15），6<15&&6>10，这个判断是错误的，返回false

3. 边界条件-无

4. 优化-无

5. 小结

除了二叉搜索树，还有一些常见的二叉树结构我们一并简单介绍，小伙伴们有个初步印象即可

平衡二叉树（平衡二叉搜索树）

本质上还是一棵二叉搜索树。
它的特点是：本身首先是一棵二叉查找树。带有平衡条件：每个结点的左右子树的高度之差的绝对值（平衡因子）最多为1。

• 图1是二叉搜索树，但不是平衡二叉树
• 图2是平衡二叉树

完全二叉树

除最后一层外，每一层上的节点数都达到最大值；
在最后一层上只缺少右边的若干结点

满二叉树

一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。