538.把二叉搜索树转换为累加树（结合自己的理解解释一下别人题解的递归部分）

538.把二叉搜索树转换为累加树（结合自己的理解解释一下别人题解的递归部分）

 题解来自labuladong。

class Solution {
public:
    int k=0;
    void Traverse(TreeNode* root)
    {
        if(!root)
            return;
        Traverse(root->right);
        k+=root->val;
        root->val=k;
        Traverse(root->left);
    }
    TreeNode* convertBST(TreeNode* root) {
        Traverse(root);
        return root;
    }
};

解决的疑惑：为什么k不用置零？是如何通过二叉树的降序遍历逐个对结点的值进行改变的？

用的是排序二叉树的降序遍历，这样可以按算出来每个节点应有的值。

后序遍历是一开始先走到最右的节点，k加上最大的节点值，因为这个节点是值最大的节点，没有比它值更大的节点所以它最后的值就是自己本身。

然后就是回退过程，回退到可以执行k+=val的节点，此时这个节点一定比刚才的节点小，那么在这个基础上k再加上自己的值作为当前节点新的值，其他节点可想而知一定又比现在的值小，那么当前节点最终的值就确定了，以此类推其他过程。

由于是降序遍历，所以对于每个节点来说，走到它这一步的时候，k一定已经加好了之前所有比它大的值了，所以k无需置零，一路走过来就可以了。