题目描述

输入两棵二叉树A，B，判断B是不是A的子结构。（我们约定空树不是任意一个树的子结构） 假如给定A为{8,8,7,9,2,#,#,#,#,4,7}，B为{8,9,2}，2个树的结构如下，可以看出B是A的子结构

题解

这种需要自己与自己相互比较的,通常需要两个递归函数.

代码

/*
	描述
	输入两棵二叉树A，B，判断B是不是A的子结构。（我们约定空树不是任意一个树的子结构）
	假如给定A为{8,8,7,9,2,#,#,#,#,4,7}，B为{8,9,2}，2个树的结构如下，可以看出B是A的子结构
*/
/*
    题解1:采用递归
    注意：该题目不能采用两个辅助数组，然后比较、二叉树中的节点是要看是在左子树还是右子树或者是根节点的。

*/
#include<iostream>
using namespace std;

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
    TreeNode(int x) :
        val(x), left(NULL), right(NULL) {
    }
};

bool issame(TreeNode* pRoot1, TreeNode* pRoot2) {
    if (!pRoot2) return true;//在递归遍历中，如果pRoot2为空，那么肯定遍历完成了
    if (!pRoot1) return false;//pRoot2为空,而对应的的节点不为空，肯定不是子树
    //if (pRoot1->val != pRoot2->val) return false;
    //if (issame(pRoot1->left, pRoot2->left) && issame(pRoot1->right, pRoot2->right))
    //    return true;
    //上面三行注释代码也可以更改为：
    if (pRoot1->val == pRoot2->val)//先检查根节点，再检查左右子节点
        return issame(pRoot1->left, pRoot2->left) && issame(pRoot1->right, pRoot2->right);
    return false;
}
bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {
    if (!pRoot1 || !pRoot2) return false;
    //按照先序遍历形式进行判断
    if (issame(pRoot1, pRoot2))
        return true;
    //以下两个判断中，通过自我递归找到正确的节点入口
    if (HasSubtree(pRoot1->left, pRoot2))
        return true;
    if (HasSubtree(pRoot1->right, pRoot2))
        return true;
    return false;
}