歡迎訪問我的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%
- 至此,解題完成,至今也沒弄明白,一個二叉樹遍歷基本功考核,怎麼就成了中級難度