博客

LeetCode全局变量问题 – 由构造二叉树发现的

今天有小伙伴（

好基友

）问了我一个问题，他在LeetCode刷到一道题，碰到一个问题一直没想通，也不知道怎么解决，于是过来让我一起看。为了说清楚这个问题，我们先看题目：

根据一棵树的前序遍历与中序遍历构造二叉树。

注意：你可以假设树中没有重复的元素。

例如，给出

前序遍历 preorder = [3,9,20,15,7] 
中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树：

    3
   / \
  9  20
    /  \
   15   7

这道题本身并不难，在LeetCode中的难度定义是中等，很显而易见的思路就是递归构造，因为前序遍历的第一个元素就是根节点，那么在中序遍历中定位到根节点后，根据中序遍历的结果就可以知道左子树和右子树中的节点数，于是就可以递归调用了。小伙伴给出的C代码如下：

struct TreeNode* buildTree(int* preorder, int preorderSize, int* inorder, int inorderSize){

	if (preorderSize <= 0) return NULL;
	if (inorderSize <= 0) return NULL;

	int idxIn;
	struct TreeNode *root = (struct TreeNode *)malloc(sizeof(struct TreeNode));
	root->val = preorder[0];

	/* find preorder[0] in inorder, the index is idxIn */
	idxIn = 0;
	while (idxIn < inorderSize) {
		if (preorder[0] == inorder[idxIn]) break;
		idxIn++;
	}

	if (idxIn != 0) { // left child exists
		root->left = buildTree(&preorder[1], idxIn, inorder, idxIn);
	} else { // no left child
		root->left = NULL;
	}

	if (idxIn != inorderSize-1) { // right child exists
		root->right = buildTree(&preorder[idxIn+1], inorderSize-idxIn-1, &inorder[idxIn+1], inorderSize-idxIn-1);
	} else { // no right child
		root->right = NULL;
	}

	return root;
}

此代码运行没有问题，在LeetCode上提交也通过了。然而小伙伴是一个有钻研精神的人，用一种方法解决问题之后并不死心，又去研究别人的解法。（嗯，此精神值得学习！）

很容易就可以发现上面的代码中是直接扫描整个中序遍历的结果并找出根节点的，因为递归调用，会重复找很多次，于是想到可以用一个哈希表来记录结果，这样只需要扫描一次，后面只要直接根据键值查询就可以了，缩短了运行时间。这也没啥，小伙伴一看思路就明白。然而，就在这个时候，他看到了另外一种解法，不用哈希表居然也实现了只扫描一次的效果，小伙伴这回惊呆了！（事实上我听他说到这里也惊呆了，还有这种操作？！）

答案是有！小伙伴给出了他按这个思路修改后的C代码：

int gIdxPre = 0;
int gIdxIn = 0;
int gLength = 0;

struct TreeNode* buildTreeHelper(int* preorder, int* inorder, long long stopVal) {
	if(gIdxPre == gLength) { // To the end, return
		return NULL;
	}
	if (inorder[gIdxIn] == stopVal) { // if equal to stop value, stop and return
		gIdxIn++;   // this value is used, go to next
		return NULL;
	}
	int rootVal = preorder[gIdxPre++];
	struct TreeNode *root = (struct TreeNode *)malloc(sizeof(struct TreeNode));
	root->val = rootVal;
	root->left = buildTreeHelper(preorder, inorder, rootVal);
	root->right = buildTreeHelper(preorder, inorder, stopVal);
	return root;
}

struct TreeNode* buildTree(int* preorder, int preorderSize, int* inorder, int inorderSize) {
	gLength = preorderSize;
	return buildTreeHelper(preorder, inorder, 0x7FFFFFFFFFF); // stop value != any value in tree
}

此方法中模拟了一个前序遍历的过程，用了一个停止值stopVal来指定子树扫描的停止位置，而初始的停止值是一个与任意树中的元素都不相等的数，所以这里用了一个long long型的超范围值。

我知道这个方法不太好理解，所以以LeetCode上的输入为例做了一个动图如下：



从图中可以看出，对输入数组只遍历了一次。

说到这里，问题终于要来了，这个代码在本地跑没问题，在LeetCode上执行代码也没问题，然而提交就报错，如下图，同样都是输入空数组（应该是第一个测试用例），点执行代码，输出与预期结果一致；点提交，就报错，而且就是这个输入的报错。




看到这个结果，本来没有LeetCode帐号的我去注册了一个号，亲测了一遍，结果一样，提交就报错。小伙伴很无辜的眼神看着我，问我代码哪里有问题，我也一脸懵啊！

想了半天，觉得还是环境的问题。毕竟我们看不到LeetCode上的其他执行部分的代码。不要去纠结为什么同样的代码同样的输入结果就不一样了，肯定是我们看不到的地方有不一致。那么怎么解决呢？

LeetCode上也无法直接调试（貌似要会员才可以），从出错结果看是堆栈溢出，那么结合代码看就是不断在malloc，也就是该返回NULL的时候没返回NULL，所以要从这个地方入手。第一个返回NULL的地方就是

if(gIdxPre == gLength)

可能这个条件没满足，于是把 == 改为了 >= ，再次提交。这次结果有了变化（有变化就好啊），变成了解答错误，出错的用例变了，可见之前的那个用例过了。



当然，执行代码的结果依然是正确的：



这就有意思了，可见就可能是这里出的问题。然而我无法调试，也没有办法加打印。怎么办呢？既然是怀疑这句的问题，那就把这两个值都好好分析一下，gLength 在函数中初始化为 preorderSize，然而 gIdxPre 在函数中并没有初始化，因为全局变量定义时已经初始化了。本着怀疑一切的精神，在 buildTree 函数中加上了一句：

gIdxPre = 0;

再次提交，还是不行，想到还有一个全局变量，于是再加上

gIdxIn = 0;

再次提交，终于成功了：

最终代码如下：

int gIdxPre = 0;
int gIdxIn = 0;
int gLength = 0;

struct TreeNode* buildTreeHelper(int* preorder, int* inorder, long long stopVal) {
	if(gIdxPre == gLength) { // To the end, return
		return NULL;
	}
	if (inorder[gIdxIn] == stopVal) { // if equal to stop value, stop and return
		gIdxIn++;   // this value is used, go to next
		return NULL;
	}
	int rootVal = preorder[gIdxPre++];
	struct TreeNode *root = (struct TreeNode *)malloc(sizeof(struct TreeNode));
	root->val = rootVal;
	root->left = buildTreeHelper(preorder, inorder, rootVal);
	root->right = buildTreeHelper(preorder, inorder, stopVal);
	return root;
}

struct TreeNode* buildTree(int* preorder, int preorderSize, int* inorder, int inorderSize) {
	gLength = preorderSize;
    gIdxPre = 0;
    gIdxIn = 0;
	return buildTreeHelper(preorder, inorder, 0x7FFFFFFFFFF); // stop value != any value in tree
}

由此过程可以发现：LeetCode 提交后运行时代码中的全局变量并没有成功初始化，保险起见，需要在函数中重新初始化全局变量。

最后，我的小伙伴带着这个结论愉快地继续去刷题了~