递归的一个问题？

Question

在做leetcode的538. Convert BST to Greater Tree题的时候，遇到了一个递归的问题。
请问：为什么这两段代码在得到的结果上有区别？

代码一：

/**
 * 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) {
        static int sum = 0;
        if (root == NULL) {
            return root;
        }

        convertBST(root->right);
        root->val += sum;
        sum = root->val;
        convertBST(root->left);

        return root;
    }
};

代码二：

/**
 * 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;
        convert(root, sum);

        return root;
    }

    void convert(TreeNode* root, int &sum) {

        if (root == NULL) {
            return ;
        }

        convert(root->right, sum);
        root->val += sum;
        sum = root->val;
        convert(root->left, sum);
    }
};

Answer 1

跑了一下，理解了你的问题.
第二个方式提交后可以AC的，在评论里我说这两个算法本质上是一样的，都是对中序遍历的一种变形(先右后左).

第一个提交失败，实际上可以猜一下原因.

2 / 212 test cases passed.

测试用例分别是：

5 2 13
2 1 3

然后第二个输入序列计算的结果是：

[25,26,23]

正确答案应该是5, 6, 3,　每个结果都在期望值的基础上增加了20,　而这里用到了static变量.　很容易猜到测试用例的调用接口的方法:

...
Solution　*s;
s->convertBST(root1);
s->convertBST(root2);

调用完第一个root1, 静态变量的状态并没有被清空.而这个遗留的数正是第一个测试用例的左树结果 20.
方式２，就没有这个问题了，每次调用接口的时候，入口处sum的值就是０.