題目描述
98. 驗證二叉搜索樹
思路
這個題思路我想的是錯的，對二叉樹的定義有所誤解堕澄。正確的理解是脯厨，根節(jié)點大于左子樹『所有』節(jié)點仰猖，并且小于右子樹『所有』節(jié)點。而我的理解是扒披，根節(jié)點大于左孩子乐导，并且小于右孩子典阵。我的理解還不到位奋渔。這個case過不了。
有了正確的理解后壮啊，代碼不會寫卒稳，怎樣描述 root大于左子樹『所有』節(jié)點這個概念？
看了答案人家都用的上下限他巨，不懂是在干嘛充坑。
呢呢告訴我，描述 root大于左子樹『所有』節(jié)點 => root大于左子樹所有節(jié)點最大值染突，
描述root小于右子樹『所有』節(jié)點 => root小于右子樹所有節(jié)點最小值捻爷。
很有道理，但是感覺實現(xiàn)起來份企，也是不夠直接也榄，有重復計算。
后來仔細想了下上下限司志，突然明白了甜紫。
如果是二叉搜索樹，中序遍歷結(jié)果是有序的呀骂远，那么每個節(jié)點都有左右鄰居吧囚霸，左右鄰居就是他的上下限。
回到上面那個圖激才，為啥這個case不能過拓型，因為6不滿足上下限（10，15）這個條件瘸恼。
用上下限來描述劣挫，就很直接，好實現(xiàn)东帅。注意一點压固，有個case是INT最大值，因此上下限要用long long靠闭。
代碼
錯誤的：
class Solution {
public:
bool isValidBST(TreeNode* root) {
if (!root) return true;
bool left = true;
bool right = true;
if (root->left) {
left = root->left->val < root->val;
}
if (root->right) {
right = root->right->val > root->val;
}
return left && right && isValidBST(root->left) && isValidBST(root->right);
}
};
正確的
class Solution {
public:
bool isValidBST(TreeNode* root) {
return within(root, LONG_MIN, LONG_MAX);
}
bool within(TreeNode* root, long long min, long long max) {
if (!root) return true;
if (root->val <= min || root->val >= max) return false;
return within(root->left, min, root->val) && within(root->right, root->val, max);
}
};
總結(jié)
思路：引入上下邊界 （這個思路我覺得挺難想到帐我，我剛看答案一下子還不能理解刘莹，上下邊界是什么玩意》俑眨可能是我思路不開闊，腦子慢半拍）
對于樹的每個節(jié)點 val 扇调，設(shè)其上下邊界 low , high矿咕。(用 long 防止 INT_MAX 溢出 )
判斷根結(jié)點時，須滿足 low < val < high 狼钮，否則返回 false
判斷左節(jié)點時碳柱，僅 上界 變化 ( 新上界為 high 與 val 較小值。又因 val 必小于 high熬芜，故新上界為 val )
判斷右節(jié)點時莲镣，僅 下界 變化 ( 同理，新下界為 val )
2021.3.15 有新的思路 更好理解
class Solution {
public:
long pre = LONG_MIN;
bool isValidBST(TreeNode* root) {
if (!root) {
return true;
}
// left
if (!isValidBST(root->left)) {
return false;
}
// root
if (pre >= root->val) {
return false;
}
pre = root->val;
// right
if (!isValidBST(root->right)) {
return false;
}
return true;
}
};
二叉搜索樹涎拉，他的中序遍歷序列是遞增的哦瑞侮！中序遍歷時，判斷當前節(jié)點是否大于中序遍歷的前一個節(jié)點鼓拧，如果大于半火，說明滿足 BST，繼續(xù)遍歷季俩；否則直接返回 false钮糖。所以用一個pre變量記錄中序遍歷的上一個節(jié)點。
