欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

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)文章

  • 分享關(guān)于JAVA 中使用Preferences讀寫(xiě)注冊(cè)表時(shí)要注意的地方

    分享關(guān)于JAVA 中使用Preferences讀寫(xiě)注冊(cè)表時(shí)要注意的地方

    這篇文章介紹了關(guān)于JAVA 中使用Preferences讀寫(xiě)注冊(cè)表時(shí)要注意的地方,有需要的朋友可以參考一下
    2013-08-08
  • Java+Appium實(shí)現(xiàn)屏幕錄制功能

    Java+Appium實(shí)現(xiàn)屏幕錄制功能

    這篇文章主要介紹了Java如何利用Appium實(shí)現(xiàn)屏幕錄制功能,本文通過(guò)實(shí)例代碼給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下
    2023-06-06
  • java判斷兩個(gè)時(shí)間是不是同一天的方法

    java判斷兩個(gè)時(shí)間是不是同一天的方法

    這篇文章主要介紹了java判斷兩個(gè)時(shí)間是不是同一天的方法,需要的朋友可以參考下
    2014-02-02
  • RocketMQ源碼分析之Broker過(guò)期消息清理機(jī)制

    RocketMQ源碼分析之Broker過(guò)期消息清理機(jī)制

    這篇文章主要為大家介紹了RocketMQ源碼分析之Broker過(guò)期消息清理機(jī)制示例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪
    2023-05-05
  • Java線程池詳細(xì)解讀

    Java線程池詳細(xì)解讀

    這篇文章主要給大家介紹了關(guān)于Java中方法使用的相關(guān)資料,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧
    2021-08-08
  • springboot配置多數(shù)據(jù)源并集成Druid和mybatis的操作

    springboot配置多數(shù)據(jù)源并集成Druid和mybatis的操作

    這篇文章主要介紹了springboot配置多數(shù)據(jù)源并集成Druid和mybatis的操作,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教
    2021-07-07
  • 如何使用spring?boot的程序主線程中異步訪問(wèn)外部接口

    如何使用spring?boot的程序主線程中異步訪問(wèn)外部接口

    CompletableFuture.supplyAsync提供了一種強(qiáng)大的工具,使您能夠以異步方式執(zhí)行操作,充分利用多核處理器和提高程序性能,同時(shí)保持代碼的清晰性和可維護(hù)性,本文給大家介紹使用spring?boot的程序主線程中異步訪問(wèn)外部接口,感興趣的朋友一起看看吧
    2023-10-10
  • Java通過(guò)索引值實(shí)現(xiàn)約瑟夫環(huán)算法

    Java通過(guò)索引值實(shí)現(xiàn)約瑟夫環(huán)算法

    這篇文章主要介紹了Java通過(guò)索引值實(shí)現(xiàn)約瑟夫環(huán),文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧
    2019-05-05
  • 淺談java對(duì)象轉(zhuǎn)json,數(shù)字精確出現(xiàn)丟失問(wèn)題

    淺談java對(duì)象轉(zhuǎn)json,數(shù)字精確出現(xiàn)丟失問(wèn)題

    下面小編就為大家?guī)?lái)一篇淺談java對(duì)象轉(zhuǎn)json, 數(shù)字精確出現(xiàn)丟失問(wèn)題。小編覺(jué)得挺不錯(cuò)的,現(xiàn)在就分享給大家,也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧
    2017-03-03
  • 教你Spring Cloud保證各個(gè)微服務(wù)之間調(diào)用安全性

    教你Spring Cloud保證各個(gè)微服務(wù)之間調(diào)用安全性

    在微服務(wù)的架構(gòu)下,系統(tǒng)會(huì)根據(jù)業(yè)務(wù)拆分為多個(gè)服務(wù),各自負(fù)責(zé)單一的職責(zé),在這樣的架構(gòu)下,我們需要確保各api的安全性,今天通過(guò)本文給大家分享Spring Cloud中如何保證各個(gè)微服務(wù)之間調(diào)用的安全性,需要的朋友參考下吧
    2021-08-08

最新評(píng)論