题目:
class Solution {
public: //本方法运用两层递归,非常巧妙
bool traversal(TreeNode* root1, TreeNode* root2){ //判断当前两个节点的递归
if(root2==nullptr) return true; //终止条件:如果递归到B节点都为空了,说明B是A的子结构
else if(root1==nullptr||root1->val!=root2->val) return false; //如果A节点为空但B的该节点不为空,或者这两个节点值不相等,直接flase
return traversal(root1->left,root2->left)&&traversal(root1->right, root2->right); //比较左右子树都满足子结构条件才可返回true
}
bool isSubStructure(TreeNode* A, TreeNode* B) {
if(A==nullptr||B==nullptr) return false; //按照题意空树不为任何树的子结构
return traversal(A, B)||isSubStructure(A->left, B)||isSubStructure(A->right, B); //B为A子结构的三种情况:1.B的起点为A的根节点 2.B是A左子树中的子结构 3.B是A右子树中的子结构
}
};
参考网站:(树) 剑指 Offer 26. 树的子结构 ——【Leetcode每日一题】
标签:26,return,Offer,子结构,TreeNode,root1,节点,root2 From: https://www.cnblogs.com/fly-smart/p/17618001.html