C++?LeetCode0538二叉搜索樹轉(zhuǎn)換累加樹示例
LeetCode 538把二叉搜索樹轉(zhuǎn)換為累加樹
力扣題目鏈接：leetcode.cn/problems/co…
給出二叉 搜索 樹的根節(jié)點，該樹的節(jié)點值各不相同，請你將其轉(zhuǎn)換為累加樹（Greater Sum Tree），使每個節(jié)點 node 的新值等于原樹中大于或等于 node.val 的值之和。
提醒一下，二叉搜索樹滿足下列約束條件：
- 節(jié)點的左子樹僅包含鍵 小于 節(jié)點鍵的節(jié)點。
- 節(jié)點的右子樹僅包含鍵 大于 節(jié)點鍵的節(jié)點。
- 左右子樹也必須是二叉搜索樹。
注意：本題和 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反向中序遍歷
二叉搜索樹有一個非常不錯的性質(zhì)，就是“中序遍歷所經(jīng)過的節(jié)點的值是非遞減的”。
同理，如果我們“反向中序遍歷（右子->根->左子）”一顆二叉搜索樹，那么我們的遍歷順序就是“非遞增”的。
我們只需要記錄一下“歷史遍歷節(jié)點的總和”，然后按照反向中序遍歷的方式去遍歷這棵二叉樹，遍歷到某個節(jié)點時，將這個節(jié)點的值修改為“這個節(jié)點的初始值 和 歷史節(jié)點總和 的 和”，同時更新“歷史遍歷節(jié)點的總和”即可。
- 時間復雜度O(n)，其中nnn是二叉樹節(jié)點的個數(shù)
- 空間復雜度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;
}
};
至于更高級的O(1)空間復雜度實現(xiàn)中序遍歷的方法，請參考官方題解
以上就是C++ LeetCode0538二叉搜索樹轉(zhuǎn)換累加樹示例的詳細內(nèi)容，更多關于C++ 二叉搜索樹轉(zhuǎn)換累加樹的資料請關注腳本之家其它相關文章！
相關文章
這篇文章主要給大家介紹了關于C++中繼承與多態(tài)的基礎虛函數(shù)類的相關資料，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧。2017-09-09
這篇文章主要為大家介紹了C++無try-catch的異常捕獲示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2022-12-12
選擇語句是C語言中的重要組成部分，該部分也比較基礎，本文將通過最通俗易懂的方式來為大家做出講解。相信通過本文的學習，讓大家一舉拿下C語言選擇語句的知識點2022-05-05
C語言中的setlinebuf()、utmpname()、rewind函數(shù)使用
這篇文章主要介紹了C語言中的setlinebuf()、utmpname()、rewind函數(shù)使用,是C語言中操作文件的一些基本函數(shù),需要的朋友可以參考下2015-08-08
這篇文章主要介紹了C程序中Ubuntu、stm32的內(nèi)存分配問題,本文給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2021-12-12
C語言實現(xiàn)選擇排序、直接插入排序、冒泡排序的示例
這篇文章主要介紹了C++實現(xiàn)選擇排序、直接插入排序、冒泡排序的代碼示例,相當簡潔直觀,也是算法和數(shù)據(jù)結構學習中的基礎,需要的朋友可以參考下2016-02-02
布爾型（Boolean），是一種類型變量類型，引用（reference）就是C++對C語言的重要擴充。引用就是某一變量（目標）的一個別名，對引用的操作與對變量直接操作完全一樣2022-04-04
本文主要介紹了C++中push_back()函數(shù)的具體使用,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧2025-01-01
在C++語言中，函數(shù)扮演著很重要的角色，不管面向過程設計，還是基于對象設計。本文主要為大家介紹了函數(shù)中重載、覆蓋和隱藏的相關知識，感興趣的小伙伴可以了解一下2022-12-12
C++?ffmpeg實現(xiàn)將視頻幀轉(zhuǎn)換成jpg或png等圖片
有時播放實時流的時候有截圖的需求，需要將解碼出來的圖片保存本地或上傳服務器，這時就需要將avframe中的數(shù)據(jù)編碼成png、jpg等格式的圖片，我們使用ffmpeg的相關編碼器就可以實現(xiàn)功能，下面就來講講具體實現(xiàn)方法吧2023-03-03