剑指Offer第17题：树的子结构

发表于 更新于 分类于

题目：输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

解题思路：遍历A树，找到一个与B树的根结点值相同的结点，开始同时遍历A、B树，判断对应结点上的值是否相同，直至遍历完B树，期间碰到A、B不同的值，则返回false。继续遍历A树，找下一个与B树根结点值相同的结点。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
bool HasSubtreeHelper(TreeNode *pRoot1, TreeNode *pRoot2) {
    if (pRoot2 == NULL) return true; //B树先遍历至空，说明B树的每一个结点都在
    if (pRoot1 == NULL) return false;
    if (pRoot1->val == pRoot2->val)
        return HasSubtreeHelper(pRoot1->left, pRoot2->left) &&  HasSubtreeHelper(pRoot1->right, pRoot2->right);
    else return false;
}

bool HasSubtree(TreeNode *pRoot1, TreeNode *pRoot2) {
    if (pRoot1 == NULL || pRoot2 == NULL) return false; //空树不是任意一个树的子结构
    return HasSubtreeHelper(pRoot1, pRoot2) || HasSubtree(pRoot1->left, pRoot2) || HasSubtree(pRoot1->right, pRoot2); // 递归判断A树的每一个结点是否可以作为B树的子结构根结点
}