题解 | #树的子结构#

树的子结构

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

树的子结构

先分析临界情况(递归的结束);

  1. A,B任何为空即放回false

  2. A,B根节点值不等时,判断A的左子树和B || A的右子树和B

  3. A和B根节点值等时,又分情况

     B左右为空,即是子树返回真。
     B都不为空时判断 A左子树B左子树 && A右子树B右子树
     B左不为空,判断 A左子树B左子树
     B右不为空,判断 A右子树B右子树
    

就算A,B值当前根节点相等,仍然B可能不匹配A,即再 || 上A左子树B || A右子树B 有一真即真

/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution {
public:
    bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {
        if(!pRoot2 || !pRoot1)return false;
        if(pRoot1->val != pRoot2->val)
            return HasSubtree(pRoot1->left, pRoot2) || HasSubtree(pRoot1->right, pRoot2);
        if(!pRoot2->left && !pRoot2->right)
            return true;
        bool flag = false;
        if(pRoot2->left && pRoot2->right)
            flag = HasSubtree(pRoot1->left, pRoot2->left) && HasSubtree(pRoot1->right, pRoot2->right);
        else if(pRoot2->left)
            flag = HasSubtree(pRoot1->left, pRoot2->left);
        else if(pRoot2->right)
            flag = HasSubtree(pRoot1->right, pRoot2->right);
       return flag ||  HasSubtree(pRoot1->left, pRoot2) || HasSubtree(pRoot1->right, pRoot2);
    }
};
全部评论

相关推荐

06-07 21:26
江南大学 C++
话不多说,直接上时间线和图片1.2024年10月底发offer,并签三方2.2025年5月底公司违约
从零开始的转码生活:希望所有签了三方但直接违约的公司都倒闭!都倒闭!都倒闭!
点赞 评论 收藏
分享
群星之怒:不是哥们,你就不好奇瘫痪三十年的老植物人是啥样的吗?
点赞 评论 收藏
分享
04-18 15:58
已编辑
门头沟学院 设计
kaoyu:这一看就不是计算机的,怎么还有个排斥洗碗?
点赞 评论 收藏
分享
评论
3
收藏
分享

创作者周榜

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