二叉搜索樹
二叉樹中的結(jié)點按照一定規(guī)則排序就變成了一顆二叉搜索樹
- 二叉搜索樹的定義：
- 它或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹:
(1) 若它的左子樹不空，則左子樹上所有結(jié)點的值均小于它的根結(jié)點的值搅吁；
(2) 若它的右子樹不空，則右子樹上所有結(jié)點的值均大于它的根結(jié)點的值；
(3) 它的左、右子樹也分別為二叉排序樹
- TIPS 有一點需要注意的是：
- 左子樹中所有點都要小于根結(jié)點锯茄，右子樹中所有點都要大于根結(jié)點。
- 下圖中圖a不是一個有效的二叉搜索樹茶没，因為結(jié)點6位于右子樹肌幽，但小于根結(jié)點10,
圖b是一個有效的二叉搜索樹
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;
//左結(jié)點存在時候判斷左結(jié)點值小于root值
if(root->left && root->left->val >= root->val)
return false;
//右結(jié)點存在時候判斷右結(jié)點值大于root值
if(root->right && root->right->val <= root->val)
return false;
//遞歸檢查左右結(jié)點
return traversal(root->left) && traversal(root->right);
}
};
- 上述代碼如果執(zhí)行上圖（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）初始函數(shù)：isValidBST（10，LONG_MIN, LONG_MAX）
（2）先遞歸遍歷左子樹：isValidBST（5探入，LONG_MIN画机，10），5<10（保證了左結(jié)點小于根結(jié)點） && 5 > LONG_MIN新症，后面的判斷結(jié)點為空的過程我們略去，不再描述响禽。
（3）然后開始遍歷右子樹isValidBST（15徒爹，10，LONG_MAX）芋类，15 <LONG_MAX && 15 >10（保證了右結(jié)點大于根結(jié)點）隆嗅，繼續(xù)執(zhí)行isValidBST（6，10侯繁，15）胖喳，6<15&&6>10，這個判斷是錯誤的贮竟，返回false
3. 邊界條件-無
4. 優(yōu)化-無
5. 小結(jié)
除了二叉搜索樹丽焊，還有一些常見的二叉樹結(jié)構我們一并簡單介紹较剃，小伙伴們有個初步印象即可
平衡二叉樹（平衡二叉搜索樹）
本質(zhì)上還是一棵二叉搜索樹。
它的特點是：本身首先是一棵二叉查找樹技健。帶有平衡條件：每個結(jié)點的左右子樹的高度之差的絕對值（平衡因子）最多為1写穴。
- 圖1是二叉搜索樹，但不是平衡二叉樹
- 圖2是平衡二叉樹
完全二叉樹
除最后一層外雌贱，每一層上的節(jié)點數(shù)都達到最大值啊送；
在最后一層上只缺少右邊的若干結(jié)點
滿二叉樹
一個二叉樹，如果每一個層的結(jié)點數(shù)都達到最大值欣孤，則這個二叉樹就是滿二叉樹馋没。
怎樣應對IT面試與筆試-（一）
怎樣應對IT面試與筆試-（二）
怎樣應對IT面試與筆試-（三）
怎樣應對IT面試與筆試-（四）
怎樣應對IT面試與筆試-（五）
怎樣應對IT面試與筆試-（五-1）
怎樣應對IT面試與筆試-（六）
怎樣應對IT面試與筆試-（七）
怎樣應對IT面試與筆試-（八）
怎樣應對IT面試與筆試-（九）
怎樣應對IT面試與筆試-（十）
怎樣應對IT面試與筆試-（十一）
怎樣應對IT面試與筆試-（十二）
怎樣應對IT面試與筆試-（十三）
怎樣應對IT面試與筆試-（十四）
怎樣應對IT面試與筆試-（十五）
怎樣應對IT面試與筆試-（十六）
