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

最新評(píng)論