Java 求解如何把二叉搜索樹(shù)轉(zhuǎn)換為累加樹(shù)

更新時(shí)間：2021年11月02日 16:12:03 作者：南淮北安

這篇文章主要介紹了Java 求解把二叉搜索樹(shù)轉(zhuǎn)換為累加樹(shù)的代碼,總之需要觀察示例節(jié)點(diǎn)的規(guī)律，需要記錄上個(gè)節(jié)點(diǎn)的情況，注意引入前驅(qū)節(jié)點(diǎn)pre，具體實(shí)例代碼跟隨小編一起看看吧

一、題目

給出二叉搜索樹(shù)的根節(jié)點(diǎn)，該樹(shù)的節(jié)點(diǎn)值各不相同，請(qǐng)你將其轉(zhuǎn)換為累加樹(shù)（Greater Sum Tree），使每個(gè)節(jié)點(diǎn) node 的新值等于原樹(shù)中大于或等于 node.val 的值之和。

提醒一下，二叉搜索樹(shù)滿足下列約束條件：
節(jié)點(diǎn)的左子樹(shù)僅包含鍵小于節(jié)點(diǎn)鍵的節(jié)點(diǎn)。
節(jié)點(diǎn)的右子樹(shù)僅包含鍵大于節(jié)點(diǎn)鍵的節(jié)點(diǎn)。
左右子樹(shù)也必須是二叉搜索樹(shù)。

在這里插入圖片描述

二、題解

觀察示例圖發(fā)現(xiàn)，樹(shù)的遍歷順序?yàn)橛?，中，左的順序，每個(gè)節(jié)點(diǎn)的值，是按照這個(gè)順序累加的狀態(tài)

在這里插入圖片描述

由于是需要累加，所以需要pre指針記錄當(dāng)前遍歷節(jié)點(diǎn)cur的前一個(gè)節(jié)點(diǎn)，方便累加

（1）確定遞歸函數(shù)及返回值

題目需要遍歷整棵樹(shù)，同時(shí)需要定義一個(gè)全局變量 pre，用來(lái)保存 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 求解如何把二叉搜索樹(shù)轉(zhuǎn)換為累加樹(shù)的文章就介紹到這了,更多相關(guān)Java 二叉搜索樹(shù)轉(zhuǎn)換為累加樹(shù)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(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的氣泡詩(shī)詞效果
這篇文章主要為大家介紹了如何利用Java實(shí)現(xiàn)帶GUI的氣泡詩(shī)詞效果，文中的示例代碼講解詳細(xì)，對(duì)我們學(xué)習(xí)Java有一定幫助，感興趣的可以了解一下
2022-12-12
使用反射方式獲取JPA Entity的屬性和值
這篇文章主要介紹了使用反射方式獲取JPA Entity的屬性和值，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教
2022-02-02
關(guān)于@GetMapping和@GetMapping(value=““)的區(qū)別
這篇文章主要介紹了關(guān)于@GetMapping和@GetMapping(value=““)的區(qū)別說(shuō)明，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教
2022-05-05
java計(jì)算工作時(shí)間除去節(jié)假日以及雙休日
這篇文章主要為大家詳細(xì)介紹了java計(jì)算工作時(shí)間除去節(jié)假日以及雙休日的方法，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
2018-06-06
java中對(duì)象和JSON格式的轉(zhuǎn)換方法代碼
JSON格式可以輕松地以面向?qū)ο蟮姆绞睫D(zhuǎn)換為Java對(duì)象,下面這篇文章主要給大家介紹了關(guān)于java中對(duì)象和JSON格式的轉(zhuǎn)換方法,文中通過(guò)代碼介紹的非常詳細(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
svn 清理失敗 (cleanup 失敗) 的快速解決方法
下面小編就為大家?guī)?lái)一篇svn 清理失敗 (cleanup 失敗) 的快速解決方法。小編覺(jué)得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧
2016-10-10
Java通過(guò)Lambda函數(shù)的方式獲取屬性名稱
這篇文章主要介紹了通過(guò)Lambda函數(shù)的方式獲取屬性名稱,實(shí)現(xiàn)步驟是通過(guò)定義一個(gè)函數(shù)式接口, 用來(lái)接收l(shuí)ambda方法引用，本文結(jié)合實(shí)例代碼給大家介紹的非常詳細(xì)，需要的朋友可以參考下
2023-10-10