力扣labuladong一刷day35天

力扣labuladong一刷day35天

文章目錄

      • 力扣labuladong一刷day35天
      • 一、98. 驗證二叉搜索樹
      • 二、700. 二叉搜索樹中的搜索
      • 三、701. 二叉搜索樹中的插入操作
      • 四、450. 刪除二叉搜索樹中的節點

一、98. 驗證二叉搜索樹

題目鏈接:https://leetcode.cn/problems/validate-binary-search-tree/
思路:校驗二叉搜索樹的合法性,簡單的想法直接遍歷判斷左右孩子與父節點值的關系即可,但是有時候會出現問題,如何 10 -> { 5, 15-> {6, 20} }。看似都滿足,其實不是的,6歸屬于10的右子樹,但是卻比10小,這也就是說每一個root只管的了他的左右孩子,但沒法把約束root的信息傳遞給左右孩子,所以我們在遍歷的時候就要攜帶上root的約束范圍向下傳遞。也就是說從上往下遍歷的過程中記錄好每一個節點的約束范圍。

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

二、700. 二叉搜索樹中的搜索

題目鏈接:https://leetcode.cn/problems/search-in-a-binary-search-tree/
思路:在二叉搜索樹中搜索值,只需要利用二叉搜索樹的特性,val<root.val 去左子樹進行搜索,val>root.val去右子樹搜索 val == root.val 返回。

class Solution {public TreeNode searchBST(TreeNode root, int val) {if (root == null) return null;if (val < root.val) return searchBST(root.left, val);if (val > root.val) return searchBST(root.right, val);return root;}
}

三、701. 二叉搜索樹中的插入操作

題目鏈接:https://leetcode.cn/problems/insert-into-a-binary-search-tree/
思路:對于二叉搜索樹的插入和查詢思路是類似的,左右判斷一路向下搜索,為node == null就找到了位置new 新節點返回就是。

class Solution {public TreeNode insertIntoBST(TreeNode root, int val) {if (root == null) return new TreeNode(val);if (val < root.val) {root.left = insertIntoBST(root.left, val);}if (val > root.val) {root.right = insertIntoBST(root.right, val);}return root;}
}

四、450. 刪除二叉搜索樹中的節點

題目鏈接:https://leetcode.cn/problems/delete-node-in-a-bst/
思路:其實對于二叉搜索樹的查找、新增、修改都是一樣的思路,對于刪除卻不一樣,有3中可能性,①、要刪除節點為葉子節點。②、要刪除節點只有一個孩子節點。③、要刪除節點有兩個孩子節點。
①、直接返回null
②、返回另一個非空的孩子節點。
③、有兩種刪除方法,可以拿當前節點的左子樹中最大值(即一路p=p.right)進行交換,然后遞歸刪除,也可以拿當前節點的右子樹中的最小值(即一路p=p.left)進行交換,然后遞歸刪除。

class Solution {public TreeNode deleteNode(TreeNode root, int key) {if (root == null) return null;if (key == root.val) {if (root.left == null && root.right == null) return null;if (root.left == null && root.right != null) return root.right;if (root.left != null && root.right == null) return root.left;TreeNode p = root.right;while (p.left != null) {p = p.left;}root.val = p.val;root.right = deleteNode(root.right, root.val);} else if (key < root.val) {root.left = deleteNode(root.left, key);}else {root.right = deleteNode(root.right, key);}return root;}
}

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

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

相關文章

【Linux】如何對文本文件進行有條件地劃分?——cut命令

cut 命令可以根據一個指定的標記&#xff08;默認是 tab&#xff09;來為文本劃分列&#xff0c;然后將此列顯示。 例如想要顯示 passwd 文件的第一列可以使用以下命令&#xff1a;cut –f 1 –d : /etc/passwd cut&#xff1a;用于從文件的每一行中提取部分內容的命令。-f 1&…

Sql server數據庫數據查詢

請查詢學生信息表的所有記錄。 答&#xff1a;查詢所需的代碼如下&#xff1a; USE 學生管理數據庫 GO SELECT * FROM 學生信息表 執行結果如下&#xff1a; 查詢學生的學號、姓名和性別。 答&#xff1a;查詢所需的代碼如下&#xff1a; USE 學生管理數據庫 GO SELE…

為什么需要 Kubernetes,它能做什么?

傳統部署時代&#xff1a; 早期&#xff0c;各個組織是在物理服務器上運行應用程序。 由于無法限制在物理服務器中運行的應用程序資源使用&#xff0c;因此會導致資源分配問題。 例如&#xff0c;如果在同一臺物理服務器上運行多個應用程序&#xff0c; 則可能會出現一個應用程…

【QED】高昂的貓 Ⅰ

目錄 題目背景題目描述輸入格式輸出格式 測試樣例樣例說明數據范圍 思路核心代碼 題目背景 這是小橘。因為它總是看起來很高傲&#xff0c;所以人送外號“高昂的貓”。 題目描述 "錒狗"的房間里放著 n n n ( 1 ≤ n ≤ 1 0 9 ) (1 \leq n \leq 10^9) (1≤n≤109)個…

C# 使用CancellationTokenSource 取消Task執行

寫在前面 在Task創建并執行后&#xff0c;如果狀態發生了變化&#xff0c;需要取消正在執行中的Task&#xff0c;除了使用主線程上的共享變量來判斷之外&#xff0c;更優雅的方式就是就是用CancellationTokenSource來取消任務的執行。 代碼實現 public static void CancelTas…

主流MQ [Kafka、RabbitMQ、ZeroMQ、RocketMQ 和 ActiveMQ]

主流MQ [Kafka、RabbitMQ、ZeroMQ、RocketMQ 和 ActiveMQ] 一&#xff0c;MQ對比圖 下面是 Kafka、RabbitMQ、ZeroMQ、RocketMQ 和 ActiveMQ 的更詳細和專業的對比&#xff1a; 特性/功能KafkaRabbitMQZeroMQRocketMQActiveMQ語言JavaErlangCJavaJava協議自有協議AMQP自有協…

算法工程師-機器學習面試題總結(6)

目錄 1.Bagging的思想是什么&#xff1f;它是降低偏差還是方差&#xff0c;為什么&#xff1f; 2.可否將RF的基分類模型由決策樹改成線性模型或者knn&#xff1f;為什么&#xff1f; 3.GBDT梯度提升和梯度下降有什么區別和聯系&#xff1f; 4.如何理解Boosting和Bagging&am…

基于ssm高校實驗室管理系統的設計與實現論文

摘 要 互聯網發展至今&#xff0c;無論是其理論還是技術都已經成熟&#xff0c;而且它廣泛參與在社會中的方方面面。它讓信息都可以通過網絡傳播&#xff0c;搭配信息管理工具可以很好地為人們提供服務。針對高校實驗室信息管理混亂&#xff0c;出錯率高&#xff0c;信息安全性…

散列卡片懸停變為整齊列表

效果展示 CSS 知識點 transform 屬性運用 頁面整體布局 <ul><li><div class"box"><img src"./user1.jpg" /><div class"content"><h4>Hamidah</h4><p>commented on your photo.<br />…

Excel 數據處理記錄

20231203 excel中的字符串以符號間隔開了&#xff0c;如何將其中的字符串挑出&#xff0c;分別放到其他單元列&#xff1a; 在Excel中打開你的表格&#xff0c;選中包含以符號間隔的字符串的單元格。在頂部菜單中&#xff0c;找到“數據”選項&#xff0c;并選擇“分列”。在…

電腦主板支持的cpu型號匯總

一、如何選擇不同的主板和對應CPU 1、看針腳&#xff1a;網上有相應的參數&#xff0c;只要CPU能安裝到主板中&#xff0c;基本就兼容&#xff0c;這主要取決CPU插槽和主板插槽十分一致。 2、看型號&#xff1a;桌面處理器&#xff0c;只有Intel和AMD兩大平臺&#xff0c;他們對…

dlib是什么?

dlib C Libraryhttp://dlib.net/ dlib是什么&#xff1f; Dlib is a modern C toolkit containing machine learning algorithms and tools for creating complex software in C to solve real world problems. It is used in both industry and academia in a wide range of…

基于SSM的高校共享單車管理系統的設計與實現論文

摘 要 網絡技術和計算機技術發展至今&#xff0c;已經擁有了深厚的理論基礎&#xff0c;并在現實中進行了充分運用&#xff0c;尤其是基于計算機運行的軟件更是受到各界的關注。加上現在人們已經步入信息時代&#xff0c;所以對于信息的宣傳和管理就很關鍵。因此高校單車租賃信…

二百一十、Hive——Flume采集的JSON數據文件寫入Hive的ODS層表后字段的數據殘缺

一、目的 在用Flume把Kafka的數據采集寫入Hive的ODS層表的HDFS文件路徑后&#xff0c;發現HDFS文件中沒問題&#xff0c;但是ODS層表中字段的數據卻有問題&#xff0c;字段中的JSON數據不全 二、Hive處理JSON數據方式 &#xff08;一&#xff09;將Flume采集Kafka的JSON數據…

【華為OD題庫-075】拼接URL-Java

題目 題目描述: 給定一個url前綴和url后綴,通過,分割。需要將其連接為一個完整的url。 如果前綴結尾和后綴開頭都沒有/&#xff0c;需要自動補上/連接符 如果前綴結尾和后綴開頭都為/&#xff0c;需要自動去重 約束:不用考慮前后綴URL不合法情況 輸入描述: url前綴(一個長度小于…

49.Go避免大量并發訪問DB、避免緩存擊穿、緩存穿透、緩存雪崩以及使用延遲雙刪保證數據一致性

文章目錄 一、在高并發下&#xff0c;如何避免大量請求直接訪問數據庫&#xff1f;二、避免緩存擊穿二、避免緩存穿透三、避免緩存雪崩四、延遲雙刪保證數據一致性五、在使用 Go 的 time.AfterFunc 函數時&#xff0c;如果刪除緩存操作失敗怎么辦&#xff1f; MySQL和 Redis是…

vue自定義指令實現按鈕只允許點擊一次

vue自定義指令實現按鈕只允許點擊一次 vue自定義指令實現按鈕只允許點擊一次 這個例子中創建了一個名為 click-once 的自定義指令&#xff0c;通過 bind 鉤子函數給元素綁定了一個點擊事件&#xff0c;并且利用一個變量 clicked 控制了按鈕只能點擊一次的行為。在點擊后會執行傳…

【ITK庫學習】使用itk庫進行圖像濾波ImageFilter:Voting濾波器

目錄 1、itkVotingBinaryImageFilter2、itkVotingBinaryHoleFillingImageFilter 洞穴充填濾波器3、itkVotingBinaryIterativeHoleFillingImageFilter4、itkLabelVotingImageFilter 1、itkVotingBinaryImageFilter 該類是一個基類&#xff0c;用于根據前景和背景像素的鄰域投票…

【數據結構實踐課設】新生報道注冊管理信息系統

目錄 1.主要框架 2.寫入文件 3.讀取文件 4.注冊學生信息 5.增加學生信息 6.刪除學生信息 7.按姓名查詢 8.按班級查詢 9.按專業查詢 10.打印學生信息 11.完整代碼 &#x1f308;嗨&#xff01;我是Filotimo__&#x1f308;。很高興與大家相識&#xff0c;希望我的博客能對你有所…

git commit語義規范

合理的應當如 [header]fix(core): remove ....(#33949) These .... RP Close #33949(可選) Header可選 代碼類 新增功能(feat) 修復缺陷(fix) 改進性能(perf) 格式化代碼(style) 優化代碼(refactor) 非代碼類 更新測試代碼(test) 部署相關變更(ci) 文檔類變更(do…