题解来自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无需置零，一路走过来就可以了。
