leetcode 98. 驗證二叉搜索樹

leetcode 98. 驗證二叉搜索樹

題目

給你一個二叉樹的根節點 root ,判斷其是否是一個有效的二叉搜索樹。

有效 二叉搜索樹定義如下:

節點的左子樹只包含 小于 當前節點的數。
節點的右子樹只包含 大于 當前節點的數。
所有左子樹和右子樹自身必須也是二叉搜索樹。

示例 1:

輸入:root = [2,1,3]
輸出:true
示例 2:

輸入:root = [5,1,4,null,null,3,6]
輸出:false
解釋:根節點的值是 5 ,但是右子節點的值是 4 。

提示:

樹中節點數目范圍在[1, 104] 內
? 2 31 -2^{31} ?231 <= Node.val <= 2 31 ? 1 2^{31} - 1 231?1

思路

其實一開始思路是正常往左右分別遍歷并且判斷當前根節點和左右子樹的大小關系,但是WA了

class Solution {public boolean isValidBST(TreeNode root) {if (root.left == null && root.right == null) {return true;}else if (root.left == null) {return root.val < root.right.val && isValidBST(root.right);}else if (root.right == null) {return root.val > root.left.val && isValidBST(root.left);}else {return root.val > root.left.val && root.val < root.right.val && isValidBST(root.left) && isValidBST(root.right);}}
}

因為上面這個沒考慮到情況
在這里插入圖片描述

所以其實應該明白中序遍歷是一個左中右的順序,對應到二叉搜索樹,自然就是一個升序序列了,所以寫了這個

class Solution {Deque<Integer> queue = new ArrayDeque<Integer>();public boolean isValidBST(TreeNode root) {dfs(root);int v = queue.pollFirst();System.out.println(v);while (! queue.isEmpty()) {int f = queue.pollFirst();if (v >= f) {return false;}v = f;}return true;}public void dfs(TreeNode root) {if (root == null) {return;}dfs(root.left);queue.offerLast(root.val);dfs(root.right);}
}

但是這個隊列的操作會拖慢運行時間,于是修改后如下

代碼

class Solution {TreeNode pre;public boolean isValidBST(TreeNode root) {if (root == null) {return true;}boolean left = isValidBST(root.left);if (pre != null && pre.val >= root.val) {return false;}pre = root;boolean right = isValidBST(root.right);return left && right;}
}

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/news/214482.shtml
繁體地址,請注明出處:http://hk.pswp.cn/news/214482.shtml
英文地址,請注明出處:http://en.pswp.cn/news/214482.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

vue3 引入 markdown編輯器

參考文檔 安裝依賴 pnpm install mavon-editor // "mavon-editor": "3.0.1",markdown 編輯器 <mavon-editor></mavon-editor>新增文本 <mavon-editor ref"editorRef" v-model"articleModel.text" codeStyle"…

Adams與Abaqus沖突問題

隨著工程仿真軟件的廣泛應用&#xff0c;Adams和Abaqus已成為眾多工程師的首選工具。然而&#xff0c;在使用過程中&#xff0c;一些用戶可能會遇到這兩個軟件之間的沖突問題&#xff0c;導致無法正常進行仿真分析。為了幫助大家解決這一難題&#xff0c;我們推出了一篇關于Ada…

Softmax回歸

一、Softmax回歸關鍵思想 1、回歸問題和分類問題的區別 Softmax回歸雖然叫“回歸”&#xff0c;但是它本質是一個分類問題。回歸是估計一個連續值&#xff0c;而分類是預測一個離散類別。 2、Softmax回歸模型 Softmax回歸跟線性回歸一樣將輸入特征與權重做線性疊加。與線性回歸…

Linux安裝Nginx并部署Vue項目

今天部署了一個Vue項目到阿里云的云服務器上&#xff0c;現記錄該過程。 1. 修改Vue項目配置 我們去項目中發送axios請求的文件里更改一下后端的接口路由&#xff1a; 2. 執行命令打包 npm run build ### 或者 yarn build 打包成功之后&#xff0c;我們會看到一個dist包&a…

[MySQL]SQL優化之索引的使用規則

&#x1f308;鍵盤敲爛&#xff0c;年薪30萬&#x1f308; 目錄 一、索引失效 &#x1f4d5;最左前綴法則 &#x1f4d5;范圍查詢> &#x1f4d5;索引列運算&#xff0c;索引失效 &#x1f4d5;前模糊匹配 &#x1f4d5;or連接的條件 &#x1f4d5;字符串類型不加 …

110. 平衡二叉樹(Java)

給定一個二叉樹&#xff0c;判斷它是否是高度平衡的二叉樹。 本題中&#xff0c;一棵高度平衡二叉樹定義為&#xff1a; 一個二叉樹每個節點 的左右兩個子樹的高度差的絕對值不超過 1 。 示例 1&#xff1a; 輸入&#xff1a;root [3,9,20,null,null,15,7] 輸出&#xff1a;t…

如何通過SPI控制Peregrine的數控衰減器

概要 Peregrine的數控衰減器PE4312是6位射頻數字步進衰減器(DSA,Digital Step Attenuator)工作頻率覆蓋1MHz~4GHz,插入損耗2dB左右,衰減步進0.5dB,最大衰減量為31.5dB,高達59dBm的IIP3提供了良好的動態性能,切換時間0.5微秒,供電電源2.3V~5.5V,邏輯控制兼容1.8V,20…

?如何使用https://www.krea.ai/來實現文生圖,圖生圖,

網址&#xff1a;https://www.krea.ai/apps/image/realtime Krea.ai 是一個強大的人工智能藝術生成器&#xff0c;可用于創建各種創意內容。它可以用來生成文本描述的圖像、將圖像轉換為其他圖像&#xff0c;甚至寫博客文章。 文本描述生成圖像 要使用 Krea.ai 生成文本描述…

設計模式——建造者模式(Java示例)

引言 生成器是一種創建型設計模式&#xff0c; 使你能夠分步驟創建復雜對象。 與其他創建型模式不同&#xff0c; 生成器不要求產品擁有通用接口。 這使得用相同的創建過程生成不同的產品成為可能。 復雜度&#xff1a; 中等 流行度&#xff1a; 流行 使用示例&#xff1a…

【conda】利用Conda創建虛擬環境,Pytorch各版本安裝教程(Ubuntu)

TOC conda 系列&#xff1a; 1. conda指令教程 2. 利用Conda創建虛擬環境&#xff0c;安裝Pytorch各版本教程(Ubuntu) 1. 利用Conda創建虛擬環境 nolonolo:~/sun/SplaTAM$ conda create -n splatam python3.10查看結果&#xff1a; (splatam) nolonolo:~/sun/SplaTAM$ cond…

Java 中的 Deque 接口及其用途

文章目錄 Deque 介紹Deque 使用雙端隊列普通隊列棧 總結 在 Java 中&#xff0c;Deque 接口是一個雙端隊列&#xff08;double-ended queue&#xff09;的數據結構&#xff0c;它支持在兩端插入和移除元素。Deque 是 “Double Ended Queue” 的縮寫&#xff0c;而且它可以同時充…

Linux系統編程(一):基本概念

參考引用 Unix和Linux操作系統有什么區別&#xff1f;一文帶你徹底搞懂posix Linux系統編程&#xff08;文章鏈接匯總&#xff09; 1. Unix 和 Linux 1.1 Unix Unix 操作系統誕生于 1969 年&#xff0c;貝爾實驗室發布了一個用 C 語言編寫的名為「Unix」的操作系統&#xff0…

【基于LSTM的電商評論情感分析:Flask與Sklearn的完美結合】

基于LSTM的電商評論情感分析&#xff1a;Flask與Sklearn的完美結合 引言數據集與爬取數據處理與可視化情感分析模型構建Flask應用搭建詞云展示創新點結論 引言 在當今數字化時代&#xff0c;電商平臺上涌現出大量的用戶評論數據。了解和分析這些評論對于企業改進產品、服務以及…

?expect命令運用于bash?

目錄 ?expect命令運用于bash? expect使用原理 expet使用場景 常用的expect命令選項 Expect腳本的結尾 常用的expect命令選參數 Expect執行方式 單一分支語法 多分支模式語法第一種 多分支模式語法第二種 在shell 中嵌套expect Shell Here Document&#xff08;內…

基于Java實驗室管理系統

基于Java實驗室管理系統 功能需求 1、實驗室設備管理&#xff1a;系統需要提供實驗室設備管理功能&#xff0c;包括設備的查詢、預訂、使用記錄、維護和報廢等。 2、實驗項目管理&#xff1a;系統需要提供實驗項目管理功能&#xff0c;包括項目的創建、審批、執行和驗收等&a…

以太坊:前世今生與未來

一、引言 以太坊&#xff0c;這個在區塊鏈領域大放異彩的名字&#xff0c;似乎已經成為了去中心化應用&#xff08;DApps&#xff09;的代名詞。從初期的萌芽到如今的繁榮發展&#xff0c;以太坊經歷了一段曲折而精彩的旅程。讓我們一起回顧一下以太坊的前世今生&#xff0c;以…

樹實驗代碼

哈夫曼樹 #include <stdio.h> #include <stdlib.h> #define MAXLEN 100typedef struct {int weight;int lchild, rchild, parent; } HTNode;typedef HTNode HT[MAXLEN]; int n;void CreatHFMT(HT T); void InitHFMT(HT T); void InputWeight(HT T); void SelectMi…

【算法專題】分治 - 快速排序

分治 - 快速排序 分治 - 快速排序1. 顏色分類2. 排序數組(快速排序)3. 數組中的第K個最大元素4. 庫存管理Ⅲ5. 排序數組(歸并排序)6. 交易逆序對的總數7. 計算右側小于當前元素的個數8. 翻轉對 分治 - 快速排序 1. 顏色分類 做題鏈接 -> Leetcode -75.顏色分類 題目&…

【華為數據之道學習筆記】3-5 規則數據治理

在業務規則管理方面&#xff0c;華為經常面對“各種業務場景業務規則不同&#xff0c;記不住&#xff0c;找不到”“大量規則在政策、流程等文件中承載&#xff0c;難以遵守”“各國規則均不同&#xff0c;IT能否一國一策、快速上線”等問題。 規則數據是結構化描述業務規則變量…

【Qt開發流程】之UI風格、預覽及QPalette使用

概述 一個優秀的應用程序不僅要有實用的功能&#xff0c;還要有一個漂亮美膩的外觀&#xff0c;這樣才能使應用程序更加友善、操作性良好&#xff0c;更加符合人體工程學。作為一個跨平臺的UI開發框架&#xff0c;Qt提供了強大而且靈活的界面外觀設計機制&#xff0c;能夠幫助…