递归的一个问题?

codinghuang
  • 142

在做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);
    }
};
回复
阅读 1.9k
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.
方式2,就没有这个问题了,每次调用接口的时候,入口处sum的值就是0.

宣传栏