神刀安全网

怎样应对IT面试与笔试-(五)

二叉搜索树

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

  • 二叉搜索树的定义:
  • 它或者是一棵空树,或者是具有下列性质的二叉树:
    (1) 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;
    (2) 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;
    (3) 它的左、右子树也分别为二叉排序树
  • TIPS 有一点需要注意的是:
  • 左子树中所有点都要小于根结点,右子树中所有点都要大于根结点。
  • 下图中图a不是一个有效的二叉搜索树,因为结点6位于右子树,但小于根结点10,
    图b是一个有效的二叉搜索树
怎样应对IT面试与笔试-(五)

BST

98. Validate Binary Search Tree

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

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

怎样应对IT面试与笔试-(五)

BST错误例子.png

3. 边界条件-无
4. 优化-无
5. 小结

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

平衡二叉树(平衡二叉搜索树)

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

怎样应对IT面试与笔试-(五)

平衡二叉树.png

  • 图1是二叉搜索树,但不是平衡二叉树
  • 图2是平衡二叉树
完全二叉树

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

怎样应对IT面试与笔试-(五)

完全二叉树

满二叉树

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

怎样应对IT面试与笔试-(五)

满二叉树.png

怎样应对IT面试与笔试-(五)

怎样应对IT面试与笔试-(一)
怎样应对IT面试与笔试-(二)
怎样应对IT面试与笔试-(三)
怎样应对IT面试与笔试-(四)
怎样应对IT面试与笔试-(五)
怎样应对IT面试与笔试-(五-1)
怎样应对IT面试与笔试-(六)
怎样应对IT面试与笔试-(七)
怎样应对IT面试与笔试-(八)
怎样应对IT面试与笔试-(九)
怎样应对IT面试与笔试-(十)
怎样应对IT面试与笔试-(十一)
怎样应对IT面试与笔试-(十二)
怎样应对IT面试与笔试-(十三)
怎样应对IT面试与笔试-(十四)
怎样应对IT面试与笔试-(十五)
怎样应对IT面试与笔试-(十六)

转载本站任何文章请注明:转载至神刀安全网,谢谢神刀安全网 » 怎样应对IT面试与笔试-(五)

分享到:更多 ()