面试题26:树的子结构

题目描述

输入两棵二叉树A和B,判断B是不是A的子结构。二叉树节点的定义如下:

1
2
3
4
5
6
struct BinaryTreeNode
{
double m_dbValue;
BinaryTreeNode* m_pLeft;
BinaryTreeNode* m_pRight;
};

解题思路

  1. 在树A中查找于根节点的值一样的节点,这实际上就是树的遍历。
  2. 判断树A中以R为根节点的子树是不是和树B具有相同的结构。

错误示范

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
bool HasSubtree(BinaryTreeNode* pRoot1, BinaryTreeNode* pRoot2) {
if (pRoot1 == nullptr || pRoot2 == nullptr) {
return false;
}

bool left, right;
// (1)
if (pRoot1->m_dbValue == pRoot2->m_dbValue) {
if (pRoot1->m_pLeft == nullptr && pRoot2->m_pLeft == nullptr) {
left = true;
} else {
left = HasSubtree(pRoot1->m_pLeft, pRoot2->m_pLeft); // (2)
//if (!left) {
// left = HasSubtree(pRoot1->m_pLeft, pRoot2);
// if (left) {
// return true;
// }
//}
}
if (pRoot1->m_pRight == nullptr && pRoot2->m_pRight == nullptr) {
right = true;
} else {
right = HasSubtree(pRoot1->m_pRight, pRoot2->m_pRight);
//if (!right) {
// right = HasSubtree(pRoot1->m_pRight, pRoot2);
// if (right) {
// return true;
// }
//}
}
return left && right;
} else {
if(pRoot1->m_pLeft && HasSubtree(pRoot1->m_pLeft, pRoot2)) { // (3)
return true;
} else if (pRoot1->m_pRight) {
return HasSubtree(pRoot1->m_pRight, pRoot2);
} else {
return false;
}
}
}

这段代码的问题在于,没有对遍历和判断进行区分,会导致在判断的时候传递了错误的信息。

以如下的二叉树A和B为例,这里的树B是树A的子结构。当我们在 (1) 这个选择分支判断树A和树B的根相同后,从 (2) 处开始对他们的子树进行判断,此时又回到 (1) 所在的分支。由于 pRoot1->m_dbValue == 8,而 pRoot2->m_dbValue == 9,从而进入 (1)else 分支 (3) 这里,此次比较本应该到这里就结束,返回 false 了。但由于这个分支的设想本是在遍历过程中根节点不一致,继续遍历。但由于没有对遍历和判断进行区分,这里会将树B的左子树作为根,传递下去。

1
2
3
4
5
6
7
      8               8
/ \ / \
8 7 9 2
/ \
9 2
/ \
4 7

此处可以对代码进行修改,增加一个布尔变量来指示本次递归,到底是在遍历,还是在比较。但由于代码设计过程中引入了大量的分支结构,逻辑十分不清晰(没错,我搞了半天才搞清楚到底是错在哪),再引入一个变量将会使代码更为复杂,所以解决这个BUG的方法,只能是将其重新写一遍

在参考了书中的解释,(自以为)理解了之后,我写出了如下的代码:

错误示范二

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
bool HasSubtree(BinaryTreeNode* pRoot1, BinaryTreeNode* pRoot2) {
if (pRoot1 == nullptr || pRoot2 == nullptr) {
return false;
}

if (pRoot1->m_dbValue != pRoot2->m_dbValue) {
if (HasSubtree(pRoot1->m_pLeft, pRoot2)) {
return true;
} else {
return HasSubtree(pRoot1->m_pRight, pRoot2);
}
} else {
// (4)
return HasSubtreeCore(pRoot1, pRoot2);
}
}

bool HasSubtreeCore(BinaryTreeNode* pRoot1, BinaryTreeNode* pRoot2) {
if (pRoot2 == nullptr) {
return true;
}
if (pRoot1 == nullptr || pRoot1->m_dbValue != pRoot2->m_dbValue) {
return false;
}
return (HasSubtreeCore(pRoot1->m_pLeft, pRoot2->m_pLeft) &&
HasSubtreeCore(pRoot1->m_pRight, pRoot2->m_pRight));
}

这段代码的问题在于,在 (4) 这里,当在树A的根节点找到与树B根节点一样的值时,不能直接返回判断的结果。因为如果这里判断的结果为否,还需要继续遍历这棵树,查找是否有其他值一样的节点,而不是直接将整个问题的结论否定掉。

正确示范

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
bool HasSubtree(BinaryTreeNode* pRoot1, BinaryTreeNode* pRoot2) {
bool result = false;
if (pRoot1 != nullptr && pRoot2 != nullptr) {
if (Equal(pRoot1->m_dbValue, pRoot2->m_dbValue)) {
result = HasSubtreeCore(pRoot1, pRoot2);
}
if (!result) {
result = HasSubtree(pRoot1->m_pLeft, pRoot2);
}
if (!result) {
result = HasSubtree(pRoot1->m_pRight, pRoot2);
}
}
return result;
}

bool HasSubtreeCore(BinaryTreeNode* pRoot1, BinaryTreeNode* pRoot2) {
if (pRoot2 == nullptr) {
return true;
}
if (pRoot1 == nullptr || !Equal(pRoot1->m_dbValue, pRoot2->m_dbValue)) {
return false;
}
return (HasSubtreeCore(pRoot1->m_pLeft, pRoot2->m_pLeft) &&
HasSubtreeCore(pRoot1->m_pRight, pRoot2->m_pRight));
}

bool Equal(double num1, double num2) {
if ((num1 - num2 > -0.0000001) && (num1 - num2 < 0.0000001)) {
return true;
} else {
return false;
}
}

反思

书中本题的讲解中也提到,在每次使用指针的时候,我们都要问问自己这个指针有没有可能是 nullptr,如果是 nullptr 则该怎么处理。另外还有个细节,在判断两个小数是否相等时,只能判断它们之差的绝对值是不是在一个很小的范围内,而不能直接使用 == 符号。

相关链接