树的子结构
- 树的子结构
输入两棵二叉树 A，BA，B，判断 BB 是不是 AA 的子结构。
我们规定空树不是任何树的子结构。
样例
树 AA：
8
/ \
8 7
/ \
9 2
/ \
4 7树 BB：
8
/ \
9 2返回 true，因为 BB 是 AA 的子结构。
算法
(二叉树，递归) O(nm)O(nm)
代码分为两个部分：
遍历树A中的所有非空节点R；
判断树A中以R为根节点的子树是不是包含和树B一样的结构，且我们从根节点开始匹配；
对于第一部分，我们直接递归遍历树A即可，遇到非空节点后，就进行第二部分的判断。
对于第二部分，我们同时从根节点开始遍历两棵子树：
如果树B中的节点为空，则表示当前分支是匹配的，返回true；
如果树A中的节点为空，但树B中的节点不为空，则说明不匹配，返回false；
如果两个节点都不为空，但数值不同，则说明不匹配，返回false；
否则说明当前这个点是匹配的，然后递归判断左子树和右子树是否分别匹配即可；
时间复杂度
最坏情况下，我们对于树A中的每个节点都要递归判断一遍，每次判断在最坏情况下需要遍历完树B中的所有节点。
所以时间复杂度是 O(nm)O(nm)，其中 nn 是树A中的节点数， mm 是树B中的节点数。
C++ 代码
/**
* 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;
if (isSame(pRoot1, pRoot2)) return true;
return hasSubtree(pRoot1->left, pRoot2) || hasSubtree(pRoot1->right, pRoot2);
}
bool isSame(TreeNode* pRoot1, TreeNode* pRoot2) {
if (!pRoot2) return true;
if (!pRoot1 || pRoot1->val != pRoot2->val) return false;
return isSame(pRoot1->left, pRoot2->left) && isSame(pRoot1->right, pRoot2->right);
}
};
