【代碼隨想錄算法訓練Day17】LeetCode 110. 平衡二叉樹、LeetCode 257.二叉樹的所有路徑、LeetCode 404.左葉子之和

Day17 二叉樹第四天

LeetCode 110. 平衡二叉樹【后序遍歷】

平衡二叉樹仍是后序遍歷,就是獲取左右子樹的高度然后作差,如果子樹就不平衡,那么就直接將-1向上傳給父節點,否則該數的高度為左右子樹高度的最大值+1。

class Solution {
public:int getHeight(TreeNode* node){if(!node) return 0;int leftHeight=getHeight(node->left);if(leftHeight==-1) return -1;int rightHeight=getHeight(node->right);if(rightHeight==-1) return -1;if(abs(rightHeight-leftHeight)>1) return -1;else return 1+max(rightHeight,leftHeight);}bool isBalanced(TreeNode* root) {return getHeight(root)==-1?false:true;}
};

LeetCode 257.二叉樹的所有路徑 【前序遍歷】

首次遇到回溯過程,我們在遍歷完之后要將元素彈出,這樣才能保證遍歷往回走時節點也彈出了。
本題有幾點需要注意:
1.遞歸推出的條件是節點左右節點均為空,而不是節點為空。
2.前序遍歷時【中】的過程,也就是記錄節點的過程要寫在遞歸結束判斷之前,否則會遺落葉子結點。
3.注意回溯的過程。

class Solution {
public:vector<int> path;vector<string> res;void travesal(TreeNode* node,vector<int>& path,vector<string>& res){path.push_back(node->val);if(!node->left && !node->right){string sPath;for(int i=0;i<path.size()-1;i++){sPath+=to_string(path[i]);sPath+="->";}sPath+=to_string(path[path.size()-1]);res.push_back(sPath);return;}if(node->left){travesal(node->left,path,res);path.pop_back();}if(node->right){travesal(node->right,path,res);path.pop_back();}}vector<string> binaryTreePaths(TreeNode* root) {if(!root) return res;travesal(root,path,res);return res;}
};

LeetCode 404.左葉子之和【后序遍歷】

本題的難點在于處理這個節點時,我們只能知道他是葉子,無法確定是否是左葉子,所以我們必須在處理他的父節點時處理這個節點,也就是如果一個節點的左孩子不為空,且這個左孩子是葉子節點,就把他的數值加到這棵樹的左葉子之和中,最后這棵樹的左葉子之和就是左右孩子的左葉子之和的和。
也就是說如果我們處理到了葉子節點,那么直接返回0即可,不必再向下遞歸一層。因為我們已經在葉子結點的上一層獲取到了左葉子的和。這樣可以減少遞歸次數,使代碼效率更高。

class Solution {
public:int sumOfLeftLeaves(TreeNode* root) {if(!root) return 0;if(!root->left && !root->right) return 0;int leftSum=sumOfLeftLeaves(root->left);if(root->left && !root->left->left && !root->left->right)leftSum=root->left->val;int rightSum=sumOfLeftLeaves(root->right);int sum=leftSum+rightSum;return sum;}
};

在寫樹和遞歸的過程中,要多注意題目的細節。

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

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

相關文章

day 38 435.無重疊區間 763.劃分字母區間 56. 合并區間 738.單調遞增的數字 968.監控二叉樹

435.無重疊區間 思路 為了使區間盡可能的重疊所以排序來使區間盡量的重疊&#xff0c;使用左邊界排序來統計重疊區間的個數與452. 用最少數量的箭引爆氣球恰好相反。 代碼 class Solution {public int eraseOverlapIntervals(int[][] intervals) {Arrays.sort(intervals,(a,…

如何在cPanel面板中開啟盜鏈保護

本周有一個客戶&#xff0c;購買Hostease的主機&#xff0c; 客戶購買的是Linux虛擬主機&#xff0c;帶cPanel面板的。詢問我們的在線客服&#xff0c;如何可以防止他的網站上的圖片不被盜用。cPanel的盜鏈保護功能可以幫助客戶防止圖片被盜鏈。 盜鏈&#xff08;Hotlinking&a…

.NET Core與.NET Framework的區別

.NET Core和.NET Framework是微軟提供的兩種主要的開發平臺&#xff0c;用于構建各種應用程序。雖然它們都基于.NET技術&#xff0c;但在架構、平臺支持、性能、開發工具和社區支持等方面存在顯著差異。本文將詳細探討.NET Core和.NET Framework的主要區別&#xff0c;幫助開發…

呆馬科技----構建智能可信的踏勘云平臺

近年來&#xff0c;隨著信息技術的快速發展&#xff0c;各個行業都在積極探索信息化的路徑&#xff0c;以提升工作效率和服務質量。智慧踏勘云平臺是基于區塊鏈和大數據技術構建的全流程智慧可信踏勘解決平臺。平臺集遠程視頻、數據顯示、工作調度、過程記錄為一體&#xff0c;…

有容量限制的車輛路徑規劃問題(Capacitated Vehicle Routing Problem)

在看matlab的時候發現了這篇文章https://www.frontiersin.org/articles/10.3389/fict.2019.00013/full 仔細閱讀一下。(英語渣渣&#xff0c;自學用) The Capacitated Vehicle Routing Problem (CVRP) is an NP-optimization problem (NPO) that has been of great interest …

圖像處理之邊緣檢測(C++)

圖像處理之邊緣檢測&#xff08;C&#xff09; 文章目錄 圖像處理之邊緣檢測&#xff08;C&#xff09;前言一、Roberts算子1.原理2.代碼實現 二、Sobel算子1.原理2.代碼實現 三、Prewitt算子1.原理2.代碼實現 四、Laplacian算子1.原理2.代碼實現 五、LOG算子1.原理2.代碼實現 …

完全匹配企業需求的替代FTP升級軟件怎么找

企業在處理數據傳輸時&#xff0c;效率和安全性是關鍵。盡管傳統的FTP曾被廣泛采用&#xff0c;但因其傳輸慢、安全性不足和難以管理等問題&#xff0c;已不再滿足現代企業的需求。許多企業正在尋找能夠滿足其需求的FTP替代方案&#xff0c;但市場上選擇眾多&#xff0c;找到合…

Python01:初入Python(Mac)

Python環境準備 下載Python&#xff1a;官網https://www.python.org/ 下載PyCharm&#xff1a;官網https://www.jetbrains.com/pycharm/download Python與PyCharm的關系 Python&#xff08;解釋器&#xff09;&#xff1a;機器語言—>翻譯人員–>翻譯成電腦能讀懂的 PyC…

STM32應用開發進階--SPI總線(7腳OLED中景園ss1306+HAL庫_硬件SPI/軟件模擬SPI)

實現目標 1、掌握SPI總線基礎知識&#xff1b; 2、會使用軟件模擬SPI總線和STM32硬件SPI總線&#xff1b; 3、 學會STM32CubeMX軟件關于SPI的配置; 4、掌握OLED顯示屏驅動&#xff1b; 5、具體目標&#xff1a;&#xff08;1&#xff09;用STM32硬件SPI驅動OLED顯示“你好…

JAVA實現定時任務 從指定時間開始每隔 n 天執行一次, 可刪除重設

本文描述的使用 Java 自帶的 ScheduledExecutorService 來實現這個業務,直接看代碼 涉及到的參數說明: ScheduledTaskManager 類負責管理定時任務的創建、取消和重設。scheduleTask 方法用于創建定時任務。它接受任務名稱、開始時間、執行間隔和任務本身作為參數。cancelTask 方…

抽煙行為檢測:從傳統巡查到智能算法

在當前人工智能和計算機視覺技術的迅猛發展下&#xff0c;基于視覺分析的抽煙行為檢測算法成為一種高效的技術手段。此類算法通常依賴于深度學習模型&#xff0c;特別是卷積神經網絡&#xff08;CNN&#xff09;&#xff0c;通過對攝像頭捕捉的視頻流進行實時分析&#xff0c;能…

在舊版 Nginx 官方 Dockerfile 上集成第三方模塊的探索

問題背景 線上生產環境用的 nginx 1.21, 然后由于新功能引入的一個問題&#xff0c;需要使用第三方模塊 ngx_http_subs_filter_module&#xff0c;目的是使用正則表達式來移除響應結果中的某些數據。 由于這個客戶的環境非常重要&#xff0c;組內的大哥們也不敢隨便升級 ngin…

網絡安全、信息安全、數據安全的定義與區別

信息安全 信息安全是指信息的保密性、完整性、可用性和真實性的保持。從定義角度來說&#xff0c;信息安全沒有嚴格標準定義&#xff0c;但從信息安全涉及的內容出發&#xff0c;信息安全確保信息存儲或傳輸中的信息&#xff0c;不被他人有意或無意的竊取與破壞。這里的“信息”…

Vue3+ts(day07:pinia)

學習源碼可以看我的個人前端學習筆記 (github.com):qdxzw/frontlearningNotes 覺得有幫助的同學&#xff0c;可以點心心支持一下哈&#xff08;筆記是根據b站上學習的尚硅谷的前端視頻【張天禹老師】&#xff0c;記錄一下學習筆記&#xff0c;用于自己復盤&#xff0c;有需要學…

ENVI光譜識別指導采礦管理者監測銅礦分布

圣地亞哥SRGIS的GIS專家Chile需要利用影像光譜信號勘察Chuquicamata的銅礦分布。 解決方案 Chuquicamata是世界上最大的斑巖銅礦分布區。SRGIS發現西部地區只有有限的礦物和貧瘠的巖石&#xff0c;但東部有銅礦分布。為了進一步測定礦藏的情況&#xff0c;他們開發出一套程序&a…

PyTorch中的形狀變換術:reshape、view與permute的區別與聯系

在PyTorch中&#xff0c;reshape、view 和 permute 都是用于改變張量&#xff08;Tensor&#xff09;形狀&#xff08;shape&#xff09;的方法&#xff0c;但它們各自的功能和用途有所不同。 view: view方法用于將張量重新整形為具有指定形狀的張量。使用view時&#xff0c;必…

NoSQL Redis配置與優化

一、關系數據庫與非關系型數據庫 1. 關系型數據庫&#xff1a; 關系型數據庫是一個結構化的數據庫&#xff0c;創建在關系模型&#xff08;二維表格模型&#xff09;基礎上&#xff0c;一般面向于記錄。 SQL 語句&#xff08;標準數據查詢語言&#xff09;就是一種基于關系型…

【Python】pandas連續變量分箱

路過了學校花店 荒野到海邊 有一種浪漫的愛 是浪費時間 徘徊到繁華世界 才發現你背影 平凡得特別 繞過了城外邊界 還是沒告別 愛錯過了太久 反而錯得完美無缺 幸福兜了一個圈 &#x1f3b5; 林宥嘉《兜圈》 import pandas as pd import numpy as np from sklearn.model_selecti…

redis核心面試題一(架構原理+RDB+AOF)

文章目錄 0. redis與mysql區別1. redis是單線程架構還是多線程架構2. redis單線程為什么這么快3. redis過期key刪除策略4. redis主從復制架構原理5. redis哨兵模式架構原理6. redis高可用集群架構原理7. redis持久化之RDB8. redis持久化之AOF9. redis持久化之混合持久化 0. red…

窮人如何翻身賺錢?不妨試試這5個冷門生意,干好了,收入相當不錯

根據統計數據&#xff0c;我國月收入超過3000元的人口已超過4億&#xff0c;這意味著仍有約10億人的月收入低于3000元。正因為如此&#xff0c;網絡上許多人都自嘲為“窮人”。 然而&#xff0c;窮人真的無法改變自己的命運嗎&#xff1f;并非如此。對于渴望賺錢的窮人來說&am…