C++?LeetCode0538二叉搜索樹轉(zhuǎn)換累加樹示例
LeetCode 538把二叉搜索樹轉(zhuǎn)換為累加樹
力扣題目鏈接:leetcode.cn/problems/co…
給出二叉 搜索 樹的根節(jié)點(diǎn),該樹的節(jié)點(diǎn)值各不相同,請(qǐng)你將其轉(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)。
- 左右子樹也必須是二叉搜索樹。
注意:本題和 1038: leetcode-cn.com/problems/bi… 相同
示例 1:
輸入:[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
輸出:[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]
示例 2:
輸入:root = [0,null,1]
輸出:[1,null,1]
示例 3:
輸入:root = [1,0,2]
輸出:[3,3,2]
示例 4:
輸入:root = [3,2,4,1]
輸出:[7,9,4,10]
提示:
方法一:DFS反向中序遍歷
二叉搜索樹有一個(gè)非常不錯(cuò)的性質(zhì),就是“中序遍歷所經(jīng)過的節(jié)點(diǎn)的值是非遞減的”。
同理,如果我們“反向中序遍歷(右子->根->左子)”一顆二叉搜索樹,那么我們的遍歷順序就是“非遞增”的。
我們只需要記錄一下“歷史遍歷節(jié)點(diǎn)的總和”,然后按照反向中序遍歷的方式去遍歷這棵二叉樹,遍歷到某個(gè)節(jié)點(diǎn)時(shí),將這個(gè)節(jié)點(diǎn)的值修改為“這個(gè)節(jié)點(diǎn)的初始值 和 歷史節(jié)點(diǎn)總和 的 和”,同時(shí)更新“歷史遍歷節(jié)點(diǎn)的總和”即可。
- 時(shí)間復(fù)雜度O(n),其中nnn是二叉樹節(jié)點(diǎn)的個(gè)數(shù)
- 空間復(fù)雜度O(n)
AC代碼
C++
class Solution { private: int total; void dfs(TreeNode* root) { if (!root) return; dfs(root->right); total = root->val = total + root->val; dfs(root->left); } public: Solution() {total = 0;} TreeNode* convertBST(TreeNode* root) { dfs(root); return root; } };
至于更高級(jí)的O(1)空間復(fù)雜度實(shí)現(xiàn)中序遍歷的方法,請(qǐng)參考官方題解
以上就是C++ LeetCode0538二叉搜索樹轉(zhuǎn)換累加樹示例的詳細(xì)內(nèi)容,更多關(guān)于C++ 二叉搜索樹轉(zhuǎn)換累加樹的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章!
相關(guān)文章
C語言實(shí)現(xiàn)職工工資管理系統(tǒng)的示例代碼
這篇文章主要為大家詳細(xì)介紹了C語言如何實(shí)現(xiàn)職工工資管理系統(tǒng),文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2022-08-08OpenMP?Parallel?Construct的實(shí)現(xiàn)原理詳解
在本篇文章當(dāng)中我們將主要分析?OpenMP?當(dāng)中的?parallel?construct?具體時(shí)如何實(shí)現(xiàn)的,以及這個(gè)?construct?調(diào)用了哪些運(yùn)行時(shí)庫函數(shù),并且詳細(xì)分析這期間的參數(shù)傳遞,需要的可以參考一下2023-01-01C++普通函數(shù)指針與成員函數(shù)指針實(shí)例解析
這篇文章主要介紹了C++普通函數(shù)指針與成員函數(shù)指針,很重要的知識(shí)點(diǎn),需要的朋友可以參考下2014-08-08解析C++函數(shù)的默認(rèn)參數(shù)和占位參數(shù)及較之C語言的拓展
這篇文章主要介紹了C++中的默認(rèn)參數(shù)和占位參數(shù)及較之C語言的拓展,需要的朋友可以參考下2016-03-03Qt+Quick實(shí)現(xiàn)播放音樂和視頻的開發(fā)
這篇文章主要為大家詳細(xì)介紹了如何利用Qt+Quick實(shí)現(xiàn)播放音樂和視頻的開發(fā),文中的示例代碼講解詳細(xì),感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下2023-03-03C++實(shí)現(xiàn)LeetCode(9.驗(yàn)證回文數(shù)字)
這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(9.驗(yàn)證回文數(shù)字),本篇文章通過簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-07-07基于OpenCv的運(yùn)動(dòng)物體檢測(cè)算法
這篇文章主要為大家詳細(xì)介紹了基于OpenCv的運(yùn)動(dòng)物體檢測(cè)算法,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2018-01-01