题目描述
输入两棵二叉树 A，B，判断 B 是不是 A 的子结构。
我们规定空树不是任何树的子结构。
数据范围
每棵树的节点数量 [0,1000]。
样例
树 A：
8 / \ 8 7 / \ 9 2 / \ 4 7
树 B：
8 / \ 9 2 • 1 • 2 • 3
返回 true，因为 B 是 A 的子结构。
方法一：二叉树，递归 O(nm)
这道题分成两个部分：
- 遍历
A树所有结点。 - 遍历时，将
A的结点下的子树和B树递归进行比较。
我们拿题目的样例举例：
第一步： 从根结点开始，发现当前结点下的子树并不与 B 树匹配。
第二步： 递归到根结点的左子树，再判断该结点下的子树是否与 B 树匹配，发现包含 B 树，直接返回 true 即可。
/** * 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; //判断p1下的子树是否包含p2下的树 if (isSame(pRoot1, pRoot2)) return true; //如果p1当前结点没有和p2匹配成功，再分别去p1的左右结点下的子树进行匹配 return hasSubtree(pRoot1->left, pRoot2) || hasSubtree(pRoot1->right, pRoot2); } //比较子树 bool isSame(TreeNode* pRoot1, TreeNode* pRoot2) { if (!pRoot2) return true; //p2要比p1树小，所以可以以p2为结束标志 //p1要包含p2，所以p1不能提前为空，否则无法与p2继续匹配 if (!pRoot1 || pRoot1->val != pRoot2->val) return false; //分别继续比较p1和p2的左子树及右子树是否匹配 return isSame(pRoot1->left, pRoot2->left) && isSame(pRoot1->right, pRoot2->right); } };
欢迎大家在评论区交流~
