首页 > 代码库 > 50. 树的子结构[subtree structure in tree]

50. 树的子结构[subtree structure in tree]

2024-07-05 19:56:08   224人阅读

【题目】

输入两棵二叉树A和B，判断B是不是A的子结构。二叉树结点的定义如下：

 C++ Code 
1
2
3
4
5
6
  
struct BinaryTreeNode
{
    int value;
     BinaryTreeNode *left;
     BinaryTreeNode *right;
};

如下图，右边的二叉树是左边二叉树的子结构。

请实现bool HasSubTree(BinaryTreeNode *parent, BinaryTreeNode *child)函数。

【分析】

可以用递归的方法求解。

递归的base case终止条件：

如果child为空，返回true；否则如果parent为空，则返回false。

然后判断parent和child的值是否相等：

（1）如果相等，则递归判断parent的左子树是否包含child的左子树，递归判断parent的右子树是否包含child的右子树；只有左右子树同时包含，返回true，否则返回false。

（2）如果不相等，递归判断parent的左子树是否包含child子树，递归判断parent的右子树是否包含child子树；只要其中之一包含，返回true，否则返回false。

【代码】

 C++ Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
  
// whether parent tree has child subtree
bool HasSubTree(BinaryTreeNode *parent, BinaryTreeNode *child)
{
    // base cases
    if (NULL == child)
        return true;
    else if(NULL == parent)
        return false;

    // whether parent and child values are equal
    if (parent->value == child->value)
     {
        bool bLeft = HasSubTree(parent->left, child->left);
        bool bRight = HasSubTree(parent->right, child->right);
        return bLeft && bRight;
     }
    else
     {
        bool bLeft = HasSubTree(parent->left, child);
        bool bRight = HasSubTree(parent->right, child);
        return bLeft || bRight;
     }
}

【参考】

http://zhedahht.blog.163.com/blog/static/25411174201011445550396/

http://blog.csdn.net/lalor/article/details/7618131

http://zhuyanfeng.com/archives/3165


联系
我们