Leetcode 538
已知一個(gè)二叉查找樹，將它轉(zhuǎn)換為一個(gè)較大樹，即所有的二叉查找樹的節(jié)點(diǎn)，賦值為該節(jié)點(diǎn)本身的值與該節(jié)點(diǎn)大的節(jié)點(diǎn)的值的和

思考與分析

較大樹中的節(jié)點(diǎn)與二叉樹的節(jié)點(diǎn)一一對(duì)應(yīng)，對(duì)于任意二叉查找樹節(jié)點(diǎn)，需要將大于該節(jié)點(diǎn)的節(jié)點(diǎn)值累加到該節(jié)點(diǎn)上。暴力的方法是，對(duì)于每個(gè)節(jié)點(diǎn)，進(jìn)行整棵樹的遍歷，將比它大的節(jié)點(diǎn)值進(jìn)行累加，時(shí)間復(fù)雜度為O(n²)

思考

按照怎么樣的方式，就可以在一次遍歷整棵樹的情況下，對(duì)節(jié)點(diǎn)值進(jìn)行累加，當(dāng)完成整棵樹的遍歷后，全部節(jié)點(diǎn)完成修改，整體時(shí)間復(fù)雜度O(n)

算法設(shè)計(jì)

修改中序遍歷二叉樹，先遍歷二叉樹右子樹，再遍歷該節(jié)點(diǎn)本身，最后遍歷二叉樹左子樹，在中序遍歷節(jié)點(diǎn)的時(shí)候?qū)⒐?jié)點(diǎn)的值累加到全局變量sum中，在中序遍歷時(shí)修改節(jié)點(diǎn)的值為sum.

void travel_tree(TreeNode *node, int &sum){
    if(!node){
        return;
    }
    travel_tree(node->right,sum);
    sum = sum + node->val;
    node->val = sum;
    travel_tree(node->left,sum);
}
class Solution{
public:
    TreeNode *convertBST(TreeNode *root){
        int sum = 0; 
        travel_tree(root, sum);
        return root;
    }
};