题解 | #树的子结构#

树的子结构

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);
    }
};
全部评论

相关推荐

05-25 10:45
西华大学 Java
Frank_zhang:没实习一个项目肯定不够,可以再做一个轮子,技术栈再补一个mq,微服务,整体再换个简历模板,暑期尽量再找一个日常实习
点赞 评论 收藏
分享
05-16 11:16
已编辑
东华理工大学 Java
牛客737698141号:盲猜几十人小公司,庙小妖风大,咋不叫她去4️⃣呢😁
点赞 评论 收藏
分享
评论
3
收藏
分享

创作者周榜

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