判断二叉树的子树（C++）

刷题平台

牛客网

题目描述

输入两棵二叉树A,B，判断B是不是A的子树。（PS：约定空树不是任意一个树的子树）

解题思路

• 若A树和B树有一个为空树，则可判断B树不是A树的子结构；
• 判断B树的根节点是否在A树中是否有相等值；
• 当A树中含有B树的根节点，然后再判断A树该节点以下的结构是否和B树结构是否相同；
• • 若B树先遍历完，而A树还没有遍历完（其中所有节点都相等），则B树为A树的子结构；
• • 若A树先遍历完，而B树还没有遍历完（其中所有节点都相等），则B树不是A树的子结构；
• • 若再遍历的时候有不相等节点，则B树不是A树的子结构；
  • 以上三步的执行顺序不能改变，

代码

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

class Solution
{
public:
    bool TreeNode *HasSubtree(TreeNode *pRoot1, TreeNode *pRoot2)
    {
        bool result = false;
        if (pRoot1 != NULL && pRoot2 != NULL)
        {
            if (pRoot1->val == pRoot2->val)// 若树A根节点和树B根节点相同
            {
                result = DoseTree1HasTree2(pRoot1, pRoot2);// 进行余下节点判断
            }
            if (!result) // A的根节点和B根节点不同，则继续判断A的左树
                result = HasSubtree(pRoot1->left, pRoot2);
            if (!result)// A的左树节点和B树的根节点不同，则继续判断A的右树
                result = HasSubtree(pRoot1->right, pRoot2);
        }
        return result;
    }
private:
    bool DoseTree1HasTree2(TreeNode *pRoot1, TreeNode *pRoot2)
    {
        if (pRoot2 == NULL) //若先遍历完B树，则B是A的子结构
            return true;
        if (pRoot1 == NULL) // 若先遍历完A树，则B不是A的子结构
            return false;
        if (pRoot1->val != pRoot2->val) //若遍历A和B时有不相等的值，则B不是A的子结构
            return false;
        // 遍历过程中 A和B都没有先遍历完，然后通过递归判断左，右子树是否相同
        return DoseTree1HasTree2(pRoot1->left, pRoot2->left) && DoseTree1HasTree2(pRoot1->right, pRoot2->right);
    }
};

其中再bool DoseTree1HasTree2()中的if(pRoot1 == NULL) return false;和if(pRoot2 == NULL) return true;交换后会出现错误。

因为bool TreeNode *HasSubtree()规定，pRoot1 和 pRoot2 不能同时为空，才能继续执行。

当交换代码的顺序后，即先判断pRoot1为空，可能会忽略一种情况，即pRoot2也为空的情况。不满足HasSubtree()中的执行条件pRoot1 != NULL && pRoot2 != NULL

以上解释来源于网络，但是自己还是想不通！

---

参考博文链接：牛客网