判断二叉树B是否是二叉树A的子树或子结构。
定义区别
- 子树：若B是A的子树，则A包含B的所有结点，并且B的叶子节点就是A的叶子节点。也就是A只要包含了B的一个结点，就得包含这个结点下的所有节点。
- 子结构：若B是A的子结构，则A包含B的所有结点，但B的叶子节点不一定是A的叶子节点。也就是子结构B是A树的任意一部分。
例如上面这棵树，4->1是A的子结构但不是子树，因为不包含2这个节点；4->1->2是A的子树，包含了节点4下的所有节点。
需要约定的是，空树不是任何一棵树的子树或子结构。
子树判断
判断B是不是A的子树，需要在A中找B。先遍历A树，遇到节点值和B树根节点相同时的节点时，判断它下面的节点是不是和B相同，这里就可以用一个递归函数来实现。递归函数的作用是：输入两个节点，判断以这两个节点为根节点的树是否完全相同。
若在A中找到了这样一个节点，和B树的值完全相同，则B就是A的子树。
//主函数，判断pRoot2是不是pRoot1的子树
bool HasSubTree(TreeNode* pRoot1, TreeNode* pRoot2)
{
//若两个树有任意一个为空树，直接返回false
if (!pRoot1 || !pRoot2) return false;
//如果pRoot1的根节点和pRoot2的根节点值相同，就需要判断这两棵树剩下的部分是否相同，所以调用递归函数IsSametree
if (pRoot1->val == pRoot2->val)
return IsSametree(pRoot1, pRoot1);
//如果pRoot1的根节点和pRoot2的根节点值不同，那么需要往下遍历A树，找它的左右节点，有任意一个节点满足条件时，B就是A的子树
else
return HasSubTree(pRoot1->left, pRoot2) || HasSubTree(pRoot1->right, pRoot2);
}
//调用函数，判断以这两个节点为根节点的树是否完全相同
bool IsSametree(TreeNode* pRoot1, TreeNode* pRoot2)
{
//如果两个节点同时为空，则是相同的树
if (!pRoot1 && !pRoot2) return true;
//如果两个节点不同时为空，则肯定不是相同的树
if (!pRoot1 || !pRoot2) return false;
//两个节点都有值，但节点值不同，那肯定不是相同的树
if (pRoot1->val != pRoot2->val)
return false;
//如果值相同，则判断他们的左右节点是否也相同（必须都相同才行）
else
return IsSametree(pRoot1->left,pRoot2->left) && IsSametree(pRoot1->right,pRoot2->right);
}
子结构判断
判断子结构，条件会略微宽松一些，因为只要B是A的一部分就好。同样的遍历A树，找到和B根节点值相同的节点，再去判断这个节点下面是不是包含B。判断是不是包含B的时候，要以B为靶子，也就是B节点为空了都行，但是不能出现节点值和B不一样，只要值不一样，那就不是子结构。这里递归函数的作用是：输入两个节点，判断判断以这两个节点为根节点的树是否是包含关系。
若在A中找到了这样一个节点，能够包含B树，则B就是A的子结构。
//主函数，判断pRoot2是不是pRoot1的子结构
bool HasSubStructure(TreeNode* pRoot1, TreeNode* pRoot2)
{
//若两个树有任意一个为空树，直接返回false
if (!pRoot1 || !pRoot2) return false;
//如果pRoot1的根节点和pRoot2的根节点值相同，就需要判断这两棵树剩下的部分是否是包含关系，所以调用递归函数IsSametree
if (pRoot1->val == pRoot2->val)
return IsSametree(pRoot1, pRoot1);
//如果pRoot1的根节点和pRoot2的根节点值不同，那么需要往下遍历A树，找它的左右节点，有任意一个节点满足条件时，B就是A的子树
else
return HasSubTree(pRoot1->left, pRoot2) || HasSubTree(pRoot1->right, pRoot2);
}
//调用函数，判断以这两个节点为根节点的树是否是包含关系，1包含2
bool IsSametree(TreeNode* pRoot1, TreeNode* pRoot2)
{
//注意这里要先判断2是不是空，因为2是空可以直接返回true
if (!pRoot2) return true;
//如果2不空，1是空的，那1肯定不包含2，返回false
if (!pRoot1) return false;
//两个节点都有值，但节点值不同，那肯定也不是包含关系
if (pRoot1->val != pRoot2->val)
return false;
//如果值相同，则判断他们的左右节点是否也是包含关系（必须都是包含关系才行）
else
return IsSametree(pRoot1->left,pRoot2->left) && IsSametree(pRoot1->right,pRoot2->right);
}
两道题结题思路是一致的，只是在判断条件上有差别，只要搞清楚了子树和子结构的区别，就能很清晰地知道怎么解题了。
网友评论