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)容，更多關(guān)于C++ 二叉搜索樹轉(zhuǎn)換累加樹的資料請關(guān)注腳本之家其它相關(guān)文章！

最新評論