[[422852]]

把二叉搜索樹轉(zhuǎn)換為累加樹

力扣題目：https://leetcode-cn.com/problems/convert-bst-to-greater-tree/

給出二叉 搜索 樹的根節(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)。左右子樹也必須是二叉搜索樹。

示例 1：

把二叉搜索樹轉(zhuǎn)換為累加樹

• 輸入：[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]

提示：

• 樹中的節(jié)點(diǎn)數(shù)介于 0 和 104 之間。
• 每個(gè)節(jié)點(diǎn)的值介于 -104 和 104 之間。
• 樹中的所有值 互不相同 。
• 給定的樹為二叉搜索樹。

思路

一看到累加樹，相信很多小伙伴都會(huì)疑惑：如何累加?遇到一個(gè)節(jié)點(diǎn)，然后在遍歷其他節(jié)點(diǎn)累加?怎么一想這么麻煩呢。

然后再發(fā)現(xiàn)這是一顆二叉搜索樹，二叉搜索樹啊，這是有序的啊。

那么有序的元素如果求累加呢?

其實(shí)這就是一棵樹，大家可能看起來有點(diǎn)別扭，換一個(gè)角度來看，這就是一個(gè)有序數(shù)組[2, 5, 13]，求從后到前的累加數(shù)組，也就是[20, 18, 13]，是不是感覺這就簡(jiǎn)單了。

為什么變成數(shù)組就是感覺簡(jiǎn)單了呢?

因?yàn)閿?shù)組大家都知道怎么遍歷啊，從后向前，挨個(gè)累加就完事了，這換成了二叉搜索樹，看起來就別扭了一些是不是。

那么知道如何遍歷這個(gè)二叉樹，也就迎刃而解了，從樹中可以看出累加的順序是右中左，所以我們需要反中序遍歷這個(gè)二叉樹，然后順序累加就可以了。

遞歸

遍歷順序如圖所示：

把二叉搜索樹轉(zhuǎn)換為累加樹

本題依然需要一個(gè)pre指針記錄當(dāng)前遍歷節(jié)點(diǎn)cur的前一個(gè)節(jié)點(diǎn)，這樣才方便做累加。

pre指針的使用技巧，我們?cè)诙鏄洌核阉鳂涞淖钚〗^對(duì)差和二叉樹：我的眾數(shù)是多少?都提到了，這是常用的操作手段。

遞歸函數(shù)參數(shù)以及返回值

這里很明確了，不需要遞歸函數(shù)的返回值做什么操作了，要遍歷整棵樹。

同時(shí)需要定義一個(gè)全局變量pre，用來保存cur節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)的數(shù)值，定義為int型就可以了。

代碼如下：

int pre; // 記錄前一個(gè)節(jié)點(diǎn)的數(shù)值 
void traversal(TreeNode* cur) 

• 確定終止條件

遇空就終止。

if (cur == NULL) return; 

• 確定單層遞歸的邏輯

注意要右中左來遍歷二叉樹， 中節(jié)點(diǎn)的處理邏輯就是讓cur的數(shù)值加上前一個(gè)節(jié)點(diǎn)的數(shù)值。

代碼如下：

traversal(cur->right);  // 右 
cur->val += pre;        // 中 
pre = cur->val; 
traversal(cur->left);   // 左 

遞歸法整體代碼如下：

class Solution { 
private: 
    int pre; // 記錄前一個(gè)節(jié)點(diǎn)的數(shù)值 
    void traversal(TreeNode* cur) { // 右中左遍歷 
        if (cur == NULL) return; 
        traversal(cur->right); 
        cur->val += pre; 
        pre = cur->val; 
        traversal(cur->left); 
    } 
public: 
    TreeNode* convertBST(TreeNode* root) { 
        pre = 0; 
        traversal(root); 
        return root; 
    } 
}; 

迭代法

迭代法其實(shí)就是中序模板題了，在二叉樹：前中后序迭代法和二叉樹：前中后序統(tǒng)一方式迭代法可以選一種自己習(xí)慣的寫法。

這里我給出其中的一種，代碼如下：

class Solution { 
private: 
    int pre; // 記錄前一個(gè)節(jié)點(diǎn)的數(shù)值 
    void traversal(TreeNode* root) { 
        stack<TreeNode*> st; 
        TreeNode* cur = root; 
        while (cur != NULL || !st.empty()) { 
            if (cur != NULL) { 
                st.push(cur); 
                cur = cur->right;   // 右 
            } else { 
                cur = st.top();     // 中 
                st.pop(); 
                cur->val += pre; 
                pre = cur->val; 
                cur = cur->left;    // 左 
            } 
        } 
    } 
public: 
    TreeNode* convertBST(TreeNode* root) { 
        pre = 0; 
        traversal(root); 
        return root; 
    } 
}; 

總結(jié)

經(jīng)歷了前面各種二叉樹增刪改查的洗禮之后，這道題目應(yīng)該比較簡(jiǎn)單了。

好了，二叉樹已經(jīng)接近尾聲了，接下來就是要對(duì)二叉樹來一個(gè)大總結(jié)了。

其他語言版本

Java

class Solution { 
    int sum; 
    public TreeNode convertBST(TreeNode root) { 
        sum = 0; 
        convertBST1(root); 
        return root; 
    } 
 
    // 按右中左順序遍歷，累加即可 
    public void convertBST1(TreeNode root) { 
        if (root == null) { 
            return; 
        } 
        convertBST1(root.right); 
        sum += root.val; 
        root.val = sum; 
        convertBST1(root.left); 
    } 
} 

Python

遞歸法

class Solution: 
    def convertBST(self, root: TreeNode) -> TreeNode: 
        def buildalist(root): 
            if not root: return None 
            buildalist(root.right)  #右中左遍歷 
            root.val += self.pre 
            self.pre = root.val 
            buildalist(root.left) 
        self.pre = 0  #記錄前一個(gè)節(jié)點(diǎn)的數(shù)值 
        buildalist(root) 
        return root 

本文轉(zhuǎn)載自微信公眾號(hào)「代碼隨想錄」，可以通過以下二維碼關(guān)注。轉(zhuǎn)載本文請(qǐng)聯(lián)系代碼隨想錄公眾號(hào)。