Tree Contain Another Tree

发表于 | 分类于

Tree Contain Another Tree(判断一棵树是否包含另外一棵树的全部拓扑结构)

题目描述：

给定两棵树的根节点T1,T2;判断T1中是否包含了T2的全部拓扑结构。

解题思路：

主要的想法还是递归解决这个问题。首先我们在寻找两棵树是否相等过程中使用先序遍历的方法。我们可以先判断当前节点的相等关系，如果相等，则递归的判断左节点和右节点；如果不等我们可以判断当前节点的左子树和右子树和目标节点的包含关系。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class treeContains1{
public:
    bool treeContains(treeNode* root1, treeNode* root2){
        if (root2 == NULL)
            return true;
        if (root1 == NULL)
            return false;
        if (root1->val == root2->val)
            return treeContains(root1->left, root2->left) && treeContains(root1->right, root2->right);
           //如果相等的情况下，我们就各自向下遍历；
        if (root1->val != root2->val)
            return treeContains(root1->left, root2) || treeContains(root1->right, root2);
            // 如果不等的情况下，我们就判断当前节点的左节点和右节点和目标节点的依存关系。
    }
};