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