剑指Offer-树的子结构

题解

 // 树的子结构
        bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
        {
            // 初始化：树A和树B的根节点pRoot1, pRoot2
            // 遍历树A，cur指向当前节点，将cur作为根节点的子树C与pRoot2作为根节点的子树进行比较，若后者是前者的子结构，则返回true否则为false
            if (!pRoot1 || !pRoot2) return false;
            return is_equ(pRoot1, pRoot2) || is_equ(pRoot1->left, pRoot2) || is_equ(pRoot1->right, pRoot2);
        }

//        // 树的先序遍历
//        void pre(TreeNode* root)
//        {
//            // 对root做点什么
//            pre(root->left);
//            pre(root->right);
//        }

        // 判断是否有相同的结构
        bool is_equ(TreeNode* pRoot1, TreeNode* pRoot2){
            // 初始化，两颗子树的根节点，pRoot1, pRoot2
            // 若pRoot1和pRoot2的内容不等，直接返回false, 若相等则递归判断其左子树和右子树是否相等
            // 若pRoot1为空，pRoot2不为空，则判为false
            // 若pRoot1不为空，pRoot2为空，则判为true
            if (!pRoot2) return true;  // pRoot2为空
            if (!pRoot1) return false;
            return (pRoot1->val==pRoot2->val) && is_equ(pRoot1->left, pRoot2->left) && is_equ(pRoot1->right, pRoot2->right);
        }

难点

1. 第7行，顶层设计，即判断树B是树A的子结构的条件：（1）树B是以树A为根节点的树的子结构；（2）树B是以树A的左子树中的子结构；（3）树B是树A中右子树的子结构；
2. 第19，26行，设计以pRoot2为根节点的树是否是以pRoot1为根节点的递归函数