【LeetCode】测试用例的覆盖

134 阅读 0 评论 89 点赞

我是靠谱客的博主想人陪嚓茶，这篇文章主要介绍【LeetCode】测试用例的覆盖，现在分享给大家，希望可以做个参考。

遇到一个简单问题：两个二叉树，如何比较完全相等。在这里：https://leetcode.com/problems/same-tree/。因为之前做了很多题目，有很多“半成品”，比如：前序遍历，中序遍历……于是想到这样的方法，把这两个树分别生成前序和中序，比较看是否相等。记得似乎不存在两个不一样的树，生成的前序和中序遍历都相等的，或者存在，但是我没发现。

代码是这样：

复制代码

void TravelA(TreeNode *root, vector<int>& vData)
	{
		if (root)
		{
			if (root->left == NULL&&root->right==NULL)
			{
				vData.push_back(root->val);
				return;
			}

if (root->left)
			{
				TravelA(root->left, vData);
			}
			else
			{
				vData.push_back(0);
			}
		
			vData.push_back(root->val);

if (root->right)
			{
				TravelA(root->right, vData);

}
			else
			{
				vData.push_back(0);
			}
		}
	}
void TravelB(TreeNode *root, vector<int>& vData)
	{
		if (root)
		{
			
			vData.push_back(root->val);
			
			if (root->left == NULL&&root->right == NULL)
			{
				return;
			}

if (root->left)
			{
				TravelA(root->left, vData);
			}
			else
			{
				vData.push_back(0);
			}

if (root->right)
			{
				TravelA(root->right, vData);

}
			else
			{
				vData.push_back(0);
			}
		}
	}

bool IsVectorSame(const vector<int>& v1,const vector<int>& v2)
	{
		if (v1.size() != v2.size())
		{
			return false;
		}

for (int i = 0; i < v1.size();i++)
		{
			if (v1[i]!=v2[i])
			{
				return false;
			}
		}

return true;
	}

bool isSameTree(TreeNode *p, TreeNode *q) {
		vector<int> vp1;
		vector<int> vq1;

TravelA(p, vp1);
		TravelA(q, vq1);

if (!IsVectorSame(vp1,vp1))
		{
			return false;
		}

vector<int> vp2;
		vector<int> vq2;

TravelB(p, vp2);
		TravelB(q, vq2);
		if (!IsVectorSame(vp2,vq2))
		{
			return false;
				
		}

return true;

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
void TravelA(TreeNode *root, vector<int>& vData)
	{
		if (root)
		{
			if (root->left == NULL&&root->right==NULL)
			{
				vData.push_back(root->val);
				return;
			}

			if (root->left)
			{
				TravelA(root->left, vData);
			}
			else
			{
				vData.push_back(0);
			}
		
			vData.push_back(root->val);

			if (root->right)
			{
				TravelA(root->right, vData);

			}
			else
			{
				vData.push_back(0);
			}
		}
	}
void TravelB(TreeNode *root, vector<int>& vData)
	{
		if (root)
		{
			
			vData.push_back(root->val);
			
			if (root->left == NULL&&root->right == NULL)
			{
				return;
			}

			if (root->left)
			{
				TravelA(root->left, vData);
			}
			else
			{
				vData.push_back(0);
			}

			if (root->right)
			{
				TravelA(root->right, vData);

			}
			else
			{
				vData.push_back(0);
			}
		}
	}

   bool IsVectorSame(const vector<int>& v1,const vector<int>& v2)
	{
		if (v1.size() != v2.size())
		{
			return false;
		}

		for (int i = 0; i < v1.size();i++)
		{
			if (v1[i]!=v2[i])
			{
				return false;
			}
		}

		return true;
	}

	bool isSameTree(TreeNode *p, TreeNode *q) {
		vector<int> vp1;
<span style="white-space:pre">		</span>vector<int> vq1;


<span style="white-space:pre">		</span>TravelA(p, vp1);
<span style="white-space:pre">		</span>TravelA(q, vq1);


<span style="white-space:pre">		</span>if (!IsVectorSame(vp1,vp1))
<span style="white-space:pre">		</span>{
<span style="white-space:pre">			</span>return false;
<span style="white-space:pre">		</span>}


<span style="white-space:pre">		</span>vector<int> vp2;
<span style="white-space:pre">		</span>vector<int> vq2;


<span style="white-space:pre">		</span>TravelB(p, vp2);
<span style="white-space:pre">		</span>TravelB(q, vq2);
<span style="white-space:pre">		</span>if (!IsVectorSame(vp2,vq2))
<span style="white-space:pre">		</span>{
<span style="white-space:pre">			</span>return false;
<span style="white-space:pre">				</span>
<span style="white-space:pre">		</span>}


<span style="white-space:pre">		</span>return true;

	}

100多行，非常壮观，恩，不错。看看性能：

也还好，处于主流水平，但是看到测试用例只有54个，似乎无法解除我的怀疑，看了下别人的写法，很直接，于是我又写了一个直接比较的递归版本：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
<span style="white-space:pre">	</span>bool isSameTree(TreeNode *p, TreeNode *q) {
		
		if (p == NULL && q == NULL)
		{
			return true;
		}

		if (p==NULL ||q==NULL)
		{
			return false;
		}

		if (p->val != q->val)
		{
			return false;
		}

		return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);

	}

基本上有用的只有一行代码，太简单了，心想这样一定更快捷了，于是提交了一下，图片就不贴了，因为是一样的。这样再次印证之前的道理，直觉是没用的，你写的代码跟实际运行的两回事。分析一下，“一行代码”的版本是对两个树递归，“100行代码”的版本是对两个树2次递归，所以花费两倍时间应该没问题，但是我估计是两棵树同步递归要花费单独递归两个树的时间，谁知道呢，不过从逻辑上是正确了，这样无论用例是否覆盖到特殊情况都正确了。

记得看过酷壳上陈皓的文章，这种开发方法叫“测试驱动”，或者“敏捷开发”，听起来很屌的样子，其实就是用测试用例完全覆盖各种情况，来摆脱人主观的局限，最大限度防止bug的产生。但是问题在于测试用例是由谁来写，写的人如果考虑不周全，就会产生bug。就像法律本身出错，就有人钻法律的空子，也就是bug产生了。他说：有的程序员一看测试通过了，就万事大吉了，代码也不优化了，就可以上线了。完全依赖于测试用例，会产生惰性，有时候会出大事情。测试通过不代表程序正确，只代表“目前没发现问题”，不过跟之前“跟着感觉走”比起来，还是从原始社会刀耕火种进化到机械化大生产了。