题解 | #树的子结构#

树的子结构

https://www.nowcoder.com/practice/6e196c44c7004d15b1610b9afca8bd88

class Solution {
private:
    TreeNode* isSubtree(TreeNode* root1, TreeNode* root2){
        /*
            @当根节点相同时,判断剩下的节点是否相同
            @return:
                返回非空指针时,说明剩下的节点不完全相同;
                返回空指针则说明是子树
        */
        if(root2 == nullptr) return nullptr; // 树B 的子节点全部走完,说明所有节点全部相同了
        else if(root1 == nullptr) return root2;// 树B未走完,但树A走完了,不对

        if(root1->val == root2->val){
            TreeNode* isLeftSubtree = isSubtree(root1->left, root2->left);
            TreeNode* isRightSubtree = isSubtree(root1->right, root2->right);
            if(isLeftSubtree == nullptr && isRightSubtree == nullptr){
                return nullptr;
            }
            else{
                return root2;
            }
        }
        else{
            return root2;
        }

        return nullptr;
    }
    bool Preoder(TreeNode* root1, TreeNode* root2){
        bool is = false;
        if(root1 == nullptr) return false;

        if(root1->val == root2->val){
            is = isSubtree(root1, root2) == nullptr;
        }
        return is || Preoder(root1->left, root2) || Preoder(root1->right, root2);
    }
public:
    bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {
        if(pRoot2 == nullptr) return false;
        return Preoder(pRoot1, pRoot2);
    }
};

全部评论

相关推荐

不愿透露姓名的神秘牛友
昨天 14:00
林子大了什么鸟都有啊,我觉得我说的已经很客气了,阴阳谁呢
牛客62656195...:应该不是阴阳吧?你第一次注册的时候boss就说你是牛人
点赞 评论 收藏
分享
06-12 16:23
已编辑
小米_软件开发(准入职员工)
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务