maxcian der TechBlog

首先複習何謂binary search tree

簡單來說，所有節點的right hand side值都比自己大；所有節點的left hand side值都比自己小。

根據以上的定義，開始剖析最小單元的binary tree，例如題目的example：

root node為5，我們則先travel它的右子樹，因我們知道右子樹一定比root node還要大，那麼root node的值則需要加上右子樹的值。

加完後，觀察此node的值(原5，加完後13)對於左子樹來說，即是所有比他大的node value的總和了，此時再去travel左子樹

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* convertBST(TreeNode* root) {
        int sum = 0;
        travel(root, sum);
        return root;
    }
    void travel(TreeNode* node, int& sum)
    {
        if (!node) return ;
        travel(node->right, sum); // traveling right-side tree first for accumulating greater-values
        node->val += sum; // plus all greater-values from the point of view of root node
        sum = node->val; // accumulating the greater-values
        travel(node->left, sum); // do the same thing for left-side tree
    }
};