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

C++?LeetCode0538二叉搜索樹轉(zhuǎn)換累加樹示例

 更新時(shí)間:2022年12月16日 15:31:53   作者:LetMeFly  
這篇文章主要為大家介紹了C++?LeetCode0538二叉搜索樹轉(zhuǎn)換累加樹示例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jì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)文章

最新評(píng)論