Java 求解如何把二叉搜索樹轉(zhuǎn)換為累加樹
一、題目
給出二叉搜索樹的根節(jié)點(diǎn)，該樹的節(jié)點(diǎn)值各不相同，請你將其轉(zhuǎn)換為累加樹（Greater Sum Tree），使每個節(jié)點(diǎn) node 的新值等于原樹中大于或等于 node.val 的值之和。
提醒一下，二叉搜索樹滿足下列約束條件：
節(jié)點(diǎn)的左子樹僅包含鍵 小于 節(jié)點(diǎn)鍵的節(jié)點(diǎn)。
節(jié)點(diǎn)的右子樹僅包含鍵 大于 節(jié)點(diǎn)鍵的節(jié)點(diǎn)。
左右子樹也必須是二叉搜索樹。
二、題解
觀察示例圖發(fā)現(xiàn)，樹的遍歷順序為右，中，左的順序，每個節(jié)點(diǎn)的值，是按照這個順序累加的狀態(tài)
由于是需要累加，所以需要pre指針記錄當(dāng)前遍歷節(jié)點(diǎn)cur的前一個節(jié)點(diǎn)，方便累加
（1）確定遞歸函數(shù)及返回值
題目需要遍歷整棵樹，同時需要定義一個全局變量 pre，用來保存 cur節(jié)點(diǎn)的前一個節(jié)點(diǎn)的數(shù)值
（2）確定遞歸終止條件
遇到空就終止
（3）確定單層遞歸的邏輯
遍歷的順序，右，中，左
三、代碼
class Solution {
// 記錄前驅(qū)節(jié)點(diǎn)
int pre = 0;
public TreeNode convertBST(TreeNode root) {
// 空節(jié)點(diǎn)終止
if (root == null) {
return root;
}
// 遍歷順序：右，中，左
convertBST(root.right);
root.val += pre;
pre = root.val;
convertBST(root.left);
return root;
}
}
四、總結(jié)
觀察示例節(jié)點(diǎn)的規(guī)律，需要記錄上個節(jié)點(diǎn)的情況，注意引入前驅(qū)節(jié)點(diǎn)pre
到此這篇關(guān)于Java 求解如何把二叉搜索樹轉(zhuǎn)換為累加樹的文章就介紹到這了,更多相關(guān)Java 二叉搜索樹轉(zhuǎn)換為累加樹內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
分享關(guān)于JAVA 中使用Preferences讀寫注冊表時要注意的地方
這篇文章介紹了關(guān)于JAVA 中使用Preferences讀寫注冊表時要注意的地方，有需要的朋友可以參考一下2013-08-08
這篇文章主要介紹了Java如何利用Appium實現(xiàn)屏幕錄制功能,本文通過實例代碼給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2023-06-06
這篇文章主要介紹了java判斷兩個時間是不是同一天的方法,需要的朋友可以參考下2014-02-02
RocketMQ源碼分析之Broker過期消息清理機(jī)制
這篇文章主要為大家介紹了RocketMQ源碼分析之Broker過期消息清理機(jī)制示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2023-05-05
這篇文章主要給大家介紹了關(guān)于Java中方法使用的相關(guān)資料,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-08-08
springboot配置多數(shù)據(jù)源并集成Druid和mybatis的操作
這篇文章主要介紹了springboot配置多數(shù)據(jù)源并集成Druid和mybatis的操作，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-07-07
如何使用spring?boot的程序主線程中異步訪問外部接口
CompletableFuture.supplyAsync提供了一種強(qiáng)大的工具，使您能夠以異步方式執(zhí)行操作，充分利用多核處理器和提高程序性能，同時保持代碼的清晰性和可維護(hù)性，本文給大家介紹使用spring?boot的程序主線程中異步訪問外部接口，感興趣的朋友一起看看吧2023-10-10
這篇文章主要介紹了Java通過索引值實現(xiàn)約瑟夫環(huán)，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2019-05-05
淺談java對象轉(zhuǎn)json,數(shù)字精確出現(xiàn)丟失問題
下面小編就為大家?guī)硪黄獪\談java對象轉(zhuǎn)json, 數(shù)字精確出現(xiàn)丟失問題。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-03-03
教你Spring Cloud保證各個微服務(wù)之間調(diào)用安全性
在微服務(wù)的架構(gòu)下，系統(tǒng)會根據(jù)業(yè)務(wù)拆分為多個服務(wù)，各自負(fù)責(zé)單一的職責(zé)，在這樣的架構(gòu)下，我們需要確保各api的安全性，今天通過本文給大家分享Spring Cloud中如何保證各個微服務(wù)之間調(diào)用的安全性，需要的朋友參考下吧2021-08-08