歡迎訪問我的GitHub 這裡分類和彙總了欣宸的全部原創(含配套源碼)：https://github.com/zq2599/blog_demos 關於LeetCode98 做這道題之前，我反覆審題，最後確認：沒錯，不存在什麼坑，這道題確實非常非常簡單，然而卻被官方定義為中等難度 這一定是送分，白撿一 ...
歡迎訪問我的GitHub
這裡分類和彙總了欣宸的全部原創(含配套源碼)：https://github.com/zq2599/blog_demos
關於LeetCode98
- 做這道題之前，我反覆審題，最後確認：沒錯，不存在什麼坑，這道題確實非常非常簡單，然而卻被官方定義為中等難度
- 這一定是送分，白撿一道中等難度題，接下來，一起來輕鬆愉快的享受解題過程吧
關於題目
- 題目：98. 驗證二叉搜索樹
- 描述
給你一個二叉樹的根節點 root ，判斷其是否是一個有效的二叉搜索樹。
有效 二叉搜索樹定義如下：
節點的左子樹只包含 小於 當前節點的數。
節點的右子樹只包含 大於 當前節點的數。
所有左子樹和右子樹自身必須也是二叉搜索樹
- 示例 1：
輸入：root = [2,1,3]
輸出：true
- 示例2：
輸入：root = [5,1,4,null,null,3,6]
輸出：false
解釋：根節點的值是 5 ，但是右子節點的值是 4 。
- 提示：
樹中節點數目範圍在[1, 104] 內
-231 <= Node.val <= 231 - 1
分析
- 簡單的說，此題的要求如下圖所示：紅色節點的值都小於100，藍色節點的值都大於100，然後，往每個子節點上套這個規則即可
- 此題有兩處需要註意：
- 對於任意節點，它的左子樹都要小於節點值，右子樹必須大於節點值，不允許等於，一旦出現就返回false
- 節點值的範圍：下限是int的最小值，上限是int的最大值
- 只要註意以上兩點，就能憑藉最基礎的二叉樹遍歷基本功解題了
解題思路
- 還是以下圖來說明
- 上圖中，不論紅色還是藍色節點，都可以設置好一個範圍區間，然後檢查這些節點在不在區間內，這就是解題思路
- 其實就是中規中矩的前序遍歷（口訣：根左右），每個節點都是先檢查自己在不在規定範圍內，然後再處理其左子樹和右子樹，在處理的時候，要重新設定範圍，對左子樹，要更新上限，對右子樹，要更新下限
- 上圖中，對紅色節點的要求是小於100，也就是說上限是100，至於下限？無所謂，那就用int的最小值-2147483648作為下限？
- 絕對不行！！！因為：節點值可能就是int的最小值！
- 同理，處理藍色節點的時候，也不能用int型的最大值2147483647作為上限
- 要用long型的最小值作為紅色的下限，long型的最大值作為上限
- 分析完成，接下來開始編碼
編碼
- 完整代碼如下，唯一要註意的就是預設上限是Long.MAX_VALUE，預設下限是Long.MIN_VALUE：
class Solution {
public boolean isValidBST(TreeNode root) {
// 左子樹，只要求不能比自己大，至於小到什麼程度都無所謂，所以用int最小值作為左側邊界
if (!isValidBST(root.left, Long.MIN_VALUE, root.val)) {
return false;
}
// 右子樹，只要求不能比自己小，至於達到什麼程度都無所謂，所以用int最大值作為右側邊界
if (!isValidBST(root.right, root.val, Long.MAX_VALUE)) {
return false;
}
return true;
}
public boolean isValidBST(TreeNode root, long min, long max) {
if (null==root) {
return true;
}
// 檢查自己
// 註意審題：左側必須比自己小，不接受等於，右側必須必自己大，不接受等於
if (root.val<=min || root.val>=max) {
return false;
}
// 左子樹，只要求不能比自己大，至於小到什麼程度都無所謂，所以用入參的最小值作為左側邊界
if (!isValidBST(root.left, min, Math.min(max, root.val))) {
return false;
}
// 右子樹，只要求不能比自己小，至於達到什麼程度都無所謂，所以用入參的最大值作為右側邊界
if (!isValidBST(root.right, Math.max(min, root.val), max)) {
return false;
}
return true;
}
}
- 提交，順利AC，用時擊敗100%
- 至此，解題完成，至今也沒弄明白，一個二叉樹遍歷基本功考核，怎麼就成了中級難度
