AcWing 37. 树的子结构
原题链接
简单
作者:
andream7
,
2020-12-23 15:32:10
,
所有人可见
,
阅读 348
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool hasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {
// 边界情况,有一颗树为空
if (!pRoot1 || !pRoot2) return false;
// 如果从根开始搜索发现两棵树有相同的子结构,则返回true
if (is_same(pRoot1, pRoot2)) return true;
// 遍历父树的每一个节点,判断是否有一个节点和子树的根匹配
return hasSubtree(pRoot1->left, pRoot2) || hasSubtree(pRoot1->right, pRoot2);
}
bool is_same(TreeNode* pRoot1, TreeNode* pRoot2) {
// 如果树B中的节点为空,则表示当前分支是匹配的,返回true
if (!pRoot2) return true;
// 如果树A中的节点为空,但树B中的节点不为空,则说明不匹配,返回false
// 如果两个节点都不为空,但数值不同,则说明不匹配,返回false
if (!pRoot1 || pRoot1->val != pRoot2->val) return false;
// 递归左右子树判断是否相等
return is_same(pRoot1->left, pRoot2->left) && is_same(pRoot1->right, pRoot2->right);
}
};