LeetCode98:驗證二叉搜索樹,居然有這麼簡單的中等難度,白撿(用時擊敗100%)

来源:https://www.cnblogs.com/bolingcavalry/archive/2023/09/12/17689785.html
-Advertisement-
Play Games

歡迎訪問我的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,然後,往每個子節點上套這個規則即可
    在這裡插入圖片描述
  • 此題有兩處需要註意:
  1. 對於任意節點,它的左子樹都要小於節點值,右子樹必須大於節點值,不允許等於,一旦出現就返回false
  2. 節點值的範圍:下限是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%
    在這裡插入圖片描述
  • 至此,解題完成,至今也沒弄明白,一個二叉樹遍歷基本功考核,怎麼就成了中級難度

歡迎關註博客園:程式員欣宸

學習路上,你不孤單,欣宸原創一路相伴...


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 在可執行文件PE文件結構中,通常我們需要用到地址轉換相關知識,PE文件針對地址的規範有三種,其中就包括了`VA`,`RVA`,`FOA`三種,這三種該地址之間的靈活轉換也是非常有用的,本節將介紹這些地址範圍如何通過編程的方式實現轉換。VA(Virtual Address,虛擬地址):它是在進程的虛擬... ...
  • 簡介 說明 本文介紹 Java 內部類持有外部類導致記憶體泄露的原因以及其解決方案。 為什麼內部類持有外部類會導致記憶體泄露 非靜態內部類會持有外部類,如果有地方引用了這個非靜態內部類,會導致外部類也被引用,垃圾回收時無法回收這個外部類(即使外部類已經沒有其他地方在使用了)。 解決方案 不要讓其他的地方 ...
  • 平衡二叉樹(Balanced Binary Tree) 平衡二叉樹是一種特殊的二叉搜索樹,它具有以下特點: 每個節點的左子樹和右子樹的高度差不超過1。 所有的子樹也都是平衡二叉樹。 通過保持平衡性,平衡二叉樹可以在最壞情況下仍然具有較好的性能,保證查找、插入和刪除操作的時間複雜度為O(log n)。 ...
  • 二叉搜索樹(Binary Search Tree,BST) 二叉搜索樹(Binary Search Tree),也稱二叉查找樹或二叉排序樹,是一種特殊的二叉樹,它滿足以下性質 對於二叉搜索樹的每個節點 左子樹中的所有節點的值都小於該節點的值 右子樹中的所有節點的值都大於(或等於)該節點的值 對於二叉 ...
  • 關註公眾號【TechLeadCloud】,分享互聯網架構、雲服務技術的全維度知識。作者擁有10+年互聯網服務架構、AI產品研發經驗、團隊管理經驗,同濟本復旦碩,復旦機器人智能實驗室成員,阿裡雲認證的資深架構師,項目管理專業人士,上億營收AI產品研發負責人。 語句 語句是Go編程語言中完成特定操作的單 ...
  • 二叉樹(binary tree) 二叉樹(Binary Tree)是一種常見的樹狀數據結構,它由一組節點組成,每個節點最多有兩個子節點,分別稱為左子節點和右子節點。二叉樹具有以下特點: 每個節點最多有兩個子節點,分別稱為左子節點和右子節點。 左子樹和右子樹也是二叉樹,它們的結構與父節點類似。 二叉樹 ...
  • 來源:https://www.cnblogs.com/zisefeizhu/p/13692782.html 前言 我司的集群時刻處於崩潰的邊緣,通過近三個月的掌握,發現我司的集群不穩定的原因有以下幾點: 1、發版流程不穩定 2、缺少監控平臺【最重要的原因】 3、缺少日誌系統 4、極度缺少有關操作文檔 ...
  • 面試題:@Transactional聲明式事務註解什麼時候會失效 前言 今天來分享一道比較有意思的面試題,“@Transactional聲明式事務註解什麼時候會失效?”。 對於這個問題,我們一起看看考察點和比較好的回答吧! 考察點 這個問題就是面試官想考察我們對@Transactional註解有沒有 ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發(一):使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說,近來想嘗試開發一款安卓APP,考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP,畢竟是使用Visual Studio開發工具,使用起來也比較的順手,結合微軟官方的教程進行了安卓 ...
  • 前言 QuestPDF 是一個開源 .NET 庫,用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫,它徹底改變了我們生成 PDF 文檔的方 ...
  • 項目地址 項目後端地址: https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址: ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址: http://tree ...
  • 話不多說,直接開乾 一.下載 1.官方鏈接下載: https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe,運行開始下載SQL server; 二. ...
  • 前言 隨著物聯網(IoT)技術的迅猛發展,MQTT(消息隊列遙測傳輸)協議憑藉其輕量級和高效性,已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫,為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog支持多種接收器用於日誌存儲,增強器用於添加屬性,LogContext管理動態屬性,支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項,適用於不同需求。 ...
  • 目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據,爬取信息時需要模擬瀏覽器行為,否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下: 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • 1.前言 什麼是熱更新 游戲或者軟體更新時,無需重新下載客戶端進行安裝,而是在應用程式啟動的情況下,在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR,Xlua,ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles,Addressable, ...
  • 本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺,其實像阿裡雲,騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後,它會送 ...
  • 通過以下方式可以高效,並保證數據同步的可靠性 1.API設計 使用RESTful設計,確保API端點明確,並使用適當的HTTP方法(如POST用於創建,PUT用於更新)。 設計清晰的請求和響應模型,以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證,確保接收到的數據符合預期格 ...