【算法訓練營Day17】二叉樹part7

文章目錄

  • 二叉樹的最近公共祖先
  • 二叉搜索樹的最近公共祖先
  • 二叉搜索樹中的插入操作
  • 刪除二叉搜索樹中的節點

二叉樹的最近公共祖先

題目鏈接:236. 二叉樹的最近公共祖先

解題邏輯:

最近公共祖先的定義為:對于有根樹 T 的兩個節點 p、q,最近公共祖先表示為一個節點 x,滿足 x 是 p、q 的祖先且 x 的深度盡可能大(一個節點也可以是它自己的祖先)

我們想要尋找兩個節點的最近公共祖先,是一個從下向上尋找的過程,那么我們可以通過遞歸中的歸來解決(向下遞,向上歸)。

我們可以通過兩種思路來解決這個問題:

  • 遞歸的返回值的傳遞
  • 回溯算法

這兩種思路都可以實現從下到上的邏輯處理。

這里我們使用遞歸返回值這種方法。

從遞歸三要素來考慮,本題采用后序遍歷:

  • 遞歸參數與返回值:遞歸的參數就是根節點、以及兩個樹節點。而遞歸的返回值是可以層層向上傳遞的,我們可以設置為set,代表當前節點的左右子樹中包含p、q中的哪個節點。
  • 遞歸的出口:當node為null的時候,返回空set即可
  • 遞歸邏輯:
    • 獲得左、右節點所具有的孩子節點
    • 創建一個新set
    • 如果當前節點是p、q中的一個則將當前節點放入set
    • 將當前set與左右節點返回的set合并
    • 如果合并之后set中同時包含p、q則說明該節點為最近的公共祖先,將其賦值給類字段
    • 否則返回set

代碼如下:

class Solution {TreeNode result = null;boolean first = true;public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {findTree(root,p.val,q.val);return result;}public Set<Integer> findTree(TreeNode node,Integer p,Integer q){if(node == null) return new HashSet<Integer>();Set<Integer> left =  findTree(node.left,p,q);Set<Integer> right =  findTree(node.right,p,q);Set<Integer> set = new HashSet<>();if(node.val == p) set.add(p);else if(node.val == q) set.add(q);set.addAll(left);set.addAll(right);if(set.contains(p) && set.contains(q) && first) {result = node;first = false;}return set;}
}

上面這種算法的核心邏輯就是:只要該節點的左右子樹中包含p、q中的任意一個就向上傳遞,當某一節點湊齊p、q那么就說明該節點是p、q最近的公共祖先。

當然上面的算法效率并不高,我們可以根據題意簡潔一下算法,將遞歸的返回值換為boolean,只要子樹中包含p或者q就返回true,代碼如下:

class Solution {TreeNode result = null;public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {findTree(root,p.val,q.val);return result;}public boolean findTree(TreeNode node,Integer p,Integer q){if(node == null) return false;boolean left =  findTree(node.left,p,q);boolean right =  findTree(node.right,p,q);if(left && right) {result = node;return true;}else if(node.val == p && (left || right)) {result = node;return true;}else if(node.val == q && (left || right)){result = node;return true;}else if(node.val == q || node.val == p) {return true;}return left || right;}
}

二叉搜索樹的最近公共祖先

題目鏈接:235. 二叉搜索樹的最近公共祖先

解題邏輯:

這個題可以直接使用上面的代碼,但是效率很低,因為沒有使用到二叉搜索樹的特性。

在二叉搜索樹中要想找到兩個節點p、q的最近公共祖先,我們可以從上往下遍歷。

  • 如果當前節點數值小于p、q兩個節點,那么說明p、q均在該節點的右子樹中,繼續往右子樹中搜索
  • 如果當前節點數值大于p、q兩個節點,那么說明p、q均在該節點的左子樹中,繼續往左子樹中搜索
  • 如果當前節點的數值在p、q兩個節點之間,那么就說明該節點就為p、q的最近公共節點(此時p、q肯定分別在該節點的左右子樹上,不會有更近的,因為如果繼續深入尋找,進入任意一邊的子樹都將失去另一邊子樹的節點)

代碼如下:

class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(root == null) return null;TreeNode left = null;TreeNode right = null;if(root.val > Math.max(p.val,q.val)) left = lowestCommonAncestor(root.left,p,q);else if(root.val < Math.min(p.val,q.val)) right = lowestCommonAncestor(root.right,p,q);else if(root.val >= Math.min(p.val,q.val) && root.val <= Math.max(p.val,q.val)) return root;if(left != null) return left;else if(right != null) return right;return null;}
}

二叉搜索樹中的插入操作

題目鏈接:701. 二叉搜索樹中的插入操作

解題邏輯:
若二叉搜索樹為空,則直接插入節點。否則若val小于跟節點值,則插入到左子樹。相反則插入到右子樹。

代碼如下:

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

刪除二叉搜索樹中的節點

題目鏈接: 450. 刪除二叉搜索樹中的節點

刪除二叉樹中的節點分為三種情況:

  • 若被刪除節點是葉子節點,則直接刪除
  • 若被刪除節點只有一棵子樹,則直接讓其子樹替代位置即可
  • 若被刪除節點有兩顆子樹,則讓被刪除節點的直接后繼(或者直接前驅)替代被刪除節點,然后從二叉搜索樹中刪除這個直接后繼(或者直接前驅),這樣就轉換成了前面兩種情況

代碼如下:

class Solution {int preNum = Integer.MAX_VALUE;public TreeNode deleteNode(TreeNode root, int key) {if(root == null) return null;TreeNode left = deleteNode(root.left,key);if(root.val == key) {if(root.left == null && root.right == null) return null;else if(root.left != null && root.right == null) return root.left;else if(root.left == null && root.right != null) return root.right;else if(root.left != null && root.right != null) {int rem = preNum;TreeNode node = deleteNode(root,rem);node.val = rem;preNum = rem;return node;}}preNum = root.val;TreeNode right = deleteNode(root.right,key);root.left = left;root.right = right;return root;}
}

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

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

相關文章

Vue插件與組件核心區別詳解

在 Vue 中&#xff0c;插件&#xff08;Plugin&#xff09; 和 組件&#xff08;Component&#xff09; 是兩種不同層次的概念&#xff0c;它們的主要區別如下&#xff1a;1. 組件 (Component) 定義&#xff1a; Vue 應用的基本構建單元&#xff0c;是可復用的 Vue 實例&#x…

基礎NLP | 02 深度學習基本原理

文章目錄 深度學習基本原理 數學基礎 線代 numpy 常用操作 導數, 梯度 梯度下降法 梯度下降代碼 GradientDescent.py 反向傳播 完整的反向傳播過程 權重更新方式 pytorch 網絡結構 全連接層 (線性層) 例子 - 手動實現模擬一個線性層 DNNforward.py 激活函數 激活函數-Sigmoid…

MySQL面試題及詳細答案 155道(001-020)

《前后端面試題》專欄集合了前后端各個知識模塊的面試題&#xff0c;包括html&#xff0c;javascript&#xff0c;css&#xff0c;vue&#xff0c;react&#xff0c;java&#xff0c;Openlayers&#xff0c;leaflet&#xff0c;cesium&#xff0c;mapboxGL&#xff0c;threejs&…

Ansible安裝與入門

目錄 Ansible ansible任務執行模式 ansible執行流程 ansible命令執行過程&#xff08;背會&#xff09; ansible的安裝方式 ansible的程序結構&#xff08;yum安裝為例&#xff09; ansible的配置文件查找順序&#xff08;背會&#xff09; 核心配置文件 ansible的配置…

【Spring】Spring Boot啟動過程源碼解析

目錄 一、啟動入口 二、SpringApplication的構造過程 2.1 設置應用類型 2.2 設置初始化器&#xff08;Initializer&#xff09; 2.2.1 獲取BootstrapRegistryInitializer對象 2.2.2 獲取ApplicationContextInitializer對象 2.3 設置監聽器&#xff08;Listener&#xff…

CDN架構全景圖

CDN架構全景圖 CDN&#xff08;內容分發網絡&#xff09;是一種通過在全球范圍內部署邊緣節點服務器&#xff0c;將內容緩存至離用戶最近的位置&#xff0c;從而加速內容分發、降低延遲并減輕源站壓力的分布式網絡架構。其核心設計目標是優化互聯網內容傳輸效率&#xff0c;提升…

【pytest高階】源碼的走讀方法及插件hook

一、pytest源碼走讀方法 依賴庫認知篇 &#x1f4e6;這是理解 pytest 源碼的 “前菜”&#xff0c;先認識 3 個超重要的小伙伴&#xff1a;iniconfig &#x1f4c4;&#xff1a;像個 “文件小管家”&#xff0c;專門負責讀取 ini 配置文件&#xff08;比如 pytest 的配置&#…

算法訓練營day32 動態規劃理論基礎、509. 斐波那契數、70. 爬樓梯、746. 使用最小花費爬樓梯

今天開始動態規劃的部分&#xff01; 其實說白了&#xff0c;動態規劃我感覺就是找類似遞歸的規律&#xff0c; 動態規劃理論基礎 動態規劃&#xff0c;英文&#xff1a;Dynamic Programming&#xff0c;簡稱DP&#xff0c;如果某一問題有很多重疊子問題&#xff0c;使用動態規…

基于神經網絡的手寫數字識別系統

基于神經網絡的手寫數字識別系統 結合模板匹配和神經網絡兩種方法進行手寫數字識別。這個系統包括圖像預處理、特征提取、神經網絡訓練和可視化分析。 %% 基于神經網絡的手寫數字識別系統%% 清理工作區 clear; clc; close all;%% 加載手寫數字數據集 % 使用MATLAB自帶的手寫數字…

機器學習?一文看懂這門熱門技術

&#x1f31f; 什么是機器學習&#xff1f;一文看懂這門熱門技術在人工智能&#xff08;AI&#xff09;的大潮中&#xff0c;機器學習&#xff08;Machine Learning, ML&#xff09; 無疑是最耀眼的明星之一。它讓計算機具備了 “自我學習” 的能力&#xff0c;讓自動駕駛、智能…

Spring的初始化鉤子

1. PostConstruct JSR-250 標準注解&#xff08;不是 Spring 獨有&#xff09;&#xff0c;用來標記 Bean 初始化完成后要執行的方法。會在 Bean 的構造方法執行完、依賴注入完成后執行。 使用實例&#xff1a; Component public class Demo {PostConstructpublic void init() …

【AI】Java生態對接大語言模型:主流框架深度解析

文章目錄1. Deep Java Library (DJL)2. LangChain4j&#xff08;LLM&#xff09;3. HuggingFace Inference API4. OpenAI Java Client技術對比矩陣架構設計建議在人工智能浪潮下&#xff0c;大語言模型&#xff08;LLM&#xff09;已成為技術核心。Java生態通過以下框架實現高效…

【06】C#入門到精通——C# 多個 .cs文件項目 同一項目下添加多個 .cs文件

文章目錄1 單個 .cs文件2 創建 多個 .cs文件2.1 添加Hero類2.1 添加ShowInfo類2.3 關于命名空間的引用2.4 所有.cs文件代碼3 test3項目文件下載1 單個 .cs文件 上一講中 描述游戲中英雄的角色 所有代碼在一個.cs文件中&#xff0c; 如果代碼很多&#xff0c;類很多&#xff0…

【MySQL基礎篇】:MySQL常用數據類型的選擇邏輯與正確使用

?感謝您閱讀本篇文章&#xff0c;文章內容是個人學習筆記的整理&#xff0c;如果哪里有誤的話還請您指正噢? ? 個人主頁&#xff1a;余輝zmh–CSDN博客 ? 文章所屬專欄&#xff1a;MySQL篇–CSDN博客 文章目錄數據類型1.數據類型分類2.數值類型int整形類型bit位類型float小…

三、搭建springCloudAlibaba2021.1版本分布式微服務-springcloud loadbalancer負載均衡

什么是負責均衡 Spring Cloud LoadBalancer是一個客戶端負載均衡器&#xff0c;類似于Ribbon&#xff0c;但是由于Ribbon已經進入維護模式&#xff0c;并且Ribbon 2并不與Ribbon 1相互兼容&#xff0c;所以Spring Cloud全家桶在Spring Cloud Commons項目中&#xff0c;添加了Sp…

Oracle不完全恢復實戰指南:從原理到操作詳解

核心提示&#xff1a;當誤刪表、日志損壞或控制文件丟失時&#xff0c;Oracle的不完全恢復是DBA最后的救命稻草。掌握關鍵恢復技術&#xff0c;可在數據災難中力挽狂瀾。一、不完全恢復核心概念 1. 核心特點 必須關閉數據庫&#xff1a;在MOUNT狀態下執行重做日志恢復權限要求&…

Linux之shell腳本篇(二)

一、shell編程之if語句引言Linux在shell編程中&#xff0c;通常都是以自上而下運行&#xff0c;但是為了提高其代碼嚴謹性&#xff0c;我們即引入了多條件 控制語句例如&#xff1a;if、for、while、case等語句&#xff0c;有時候針對條件我們還會結合正則表達式去運用。將這些…

如何在android framewrok dump camera data

實現dump 函數 實現1 void dumpBufferToFile(buffer_handle_t* buffer, int width, int height, int frameNum) {void* data NULL;GraphicBufferMapper::getInstance().lock(*buffer, GRALLOC_USAGE_SW_READ_OFTEN, Rect(width, height), &data);char filename[128];sprin…

機器學習中的可解釋性:深入理解SHAP值及其應用

機器學習可解釋性的重要性在人工智能技術快速發展的2025年&#xff0c;機器學習模型已經深度滲透到醫療診斷、金融風控、司法量刑等關鍵領域。然而&#xff0c;隨著模型復雜度的不斷提升&#xff0c;一個根本性矛盾日益凸顯&#xff1a;模型預測性能的提升往往以犧牲可解釋性為…

.NET9 使用 OData 協議項目實戰

.NET 中 ODate 協議介紹 OData(Open Data Protocol) 是一個開放的 Web 協議&#xff0c;用于查詢和更新數據。在 .NET 生態系統中&#xff0c;OData 被廣泛支持和使用。 主要特性 1. 統一的數據訪問方式 提供標準化的查詢語法支持 CRUD 操作支持元數據描述 2. 查詢能力 標…