Java 求解如何把二叉搜索樹轉(zhuǎn)換為累加樹
一、題目
給出二叉搜索樹的根節(jié)點(diǎn)，該樹的節(jié)點(diǎn)值各不相同，請你將其轉(zhuǎn)換為累加樹（Greater Sum Tree），使每個(gè)節(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)，樹的遍歷順序?yàn)橛?，中，左的順序，每個(gè)節(jié)點(diǎn)的值，是按照這個(gè)順序累加的狀態(tài)
由于是需要累加，所以需要pre指針記錄當(dāng)前遍歷節(jié)點(diǎn)cur的前一個(gè)節(jié)點(diǎn)，方便累加
（1）確定遞歸函數(shù)及返回值
題目需要遍歷整棵樹，同時(shí)需要定義一個(gè)全局變量 pre，用來保存 cur節(jié)點(diǎn)的前一個(gè)節(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ī)律，需要記錄上個(gè)節(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)文章
Spring Boot中配置文件application.properties使用
這篇文章主要介紹了Spring Boot中配置文件application.properties使用及spring boot讀取application.properties文件的方式，需要的朋友參考下吧2018-01-01
Java實(shí)現(xiàn)真假隨機(jī)數(shù)詳解
偽隨機(jī)數(shù)和真隨機(jī)數(shù)是計(jì)算機(jī)科學(xué)和統(tǒng)計(jì)學(xué)中非常重要的概念,理解它們之間的差異有助于選擇合適的隨機(jī)數(shù)生成方案,本文將使用Java實(shí)現(xiàn)真假隨機(jī)數(shù),感興趣的可以了解下2024-11-11
這篇文章主要為大家介紹了如何利用Java實(shí)現(xiàn)帶GUI的氣泡詩詞效果，文中的示例代碼講解詳細(xì)，對我們學(xué)習(xí)Java有一定幫助，感興趣的可以了解一下2022-12-12
這篇文章主要介紹了使用反射方式獲取JPA Entity的屬性和值，具有很好的參考價(jià)值，希望對大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2022-02-02
關(guān)于@GetMapping和@GetMapping(value=““)的區(qū)別
這篇文章主要介紹了關(guān)于@GetMapping和@GetMapping(value=““)的區(qū)別說明，具有很好的參考價(jià)值，希望對大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2022-05-05
java計(jì)算工作時(shí)間除去節(jié)假日以及雙休日
這篇文章主要為大家詳細(xì)介紹了java計(jì)算工作時(shí)間除去節(jié)假日以及雙休日的方法，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2018-06-06
JSON格式可以輕松地以面向?qū)ο蟮姆绞睫D(zhuǎn)換為Java對象,下面這篇文章主要給大家介紹了關(guān)于java中對象和JSON格式的轉(zhuǎn)換方法,文中通過代碼介紹的非常詳細(xì),需要的朋友可以參考下2023-12-12
SpringBoot+Hutool+thymeleaf完成導(dǎo)出Excel的實(shí)現(xiàn)方法
這篇文章主要介紹了SpringBoot+Hutool+thymeleaf完成導(dǎo)出Excel,本篇示例當(dāng)中不僅僅有后端，而且還提供了前端html，html當(dāng)中利用js將后端 輸出流直接下載為文件，需要的朋友可以參考下2022-03-03
下面小編就為大家?guī)硪黄猻vn 清理失敗 (cleanup 失敗) 的快速解決方法。小編覺得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧2016-10-10
這篇文章主要介紹了通過Lambda函數(shù)的方式獲取屬性名稱,實(shí)現(xiàn)步驟是通過定義一個(gè)函數(shù)式接口, 用來接收lambda方法引用，本文結(jié)合實(shí)例代碼給大家介紹的非常詳細(xì)，需要的朋友可以參考下2023-10-10