赞
踩
一、题目
二、分析
要判断一个树是不是另一个树的子树,这里边存在两个递归–
第一个:确定一个根节点,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==NULL) return false; //空树不是任意一个树的子树 if(pRoot1==NULL && pRoot2!=NULL) return false; if(isSon(pRoot1,pRoot2)) return true; if(HasSubtree(pRoot1->left, pRoot2)) return true; if(HasSubtree(pRoot1->right, pRoot2)) return true; return false; } bool isSon(TreeNode* root1, TreeNode* root2){ //第二个递归,比较这个树上的每一个节点 if(root2==NULL) return true; if(root1==NULL && root2!=NULL) return false; if(root1->val!=root2->val) return false; bool left=isSon(root1->left, root2->left); bool right=isSon(root1->right, root2->right); if(left && right ) return true; return false; } };
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。