首页 > 试题广场 >

拓扑结构相同子树

[编程题]拓扑结构相同子树
  • 热度指数：4710 时间限制：C/C++ 3秒，其他语言6秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解

对于两棵彼此独立的二叉树A和B，请编写一个高效算法，检查A中是否存在一棵子树与B树的拓扑结构完全相同。

给定两棵二叉树的头结点A和B，请返回一个bool值，代表A中是否存在一棵同构于B的子树。


说明：本题目包含复杂数据结构TreeNode，点此查看相关信息
算法知识视频讲解
添加回答
牛客787908号头像 牛客787908号
本题目解题思路：
（1）构建二叉树 （2）在树A中找到和B的根结点的值一样的结点N（递归遍历）（3）再判断树A中以N为根结点的子树是不是包括和树B一样的结构。
源代码：
public class HasSubTree {
// 定义二叉树数据结构
class TreeNode {
TreeNode left;
TreeNode right;
int val;

public TreeNode(int val) {
this.val = val;
}

public TreeNode getLeft() {
return left;
}

public TreeNode getRight() {
return right;
}

public int getVal() {
return val;
}

}

/***
* 判断两棵树是否为空
* 
* @param pTreeHead1
* @param pTreeHead2
* @return
*/
boolean hasSubTree(TreeNode pTreeHead1, TreeNode pTreeHead2) {
if ((pTreeHead1 == null && pTreeHead2 != null)
|| (pTreeHead1 != null && pTreeHead2 == null))
return false;
if (pTreeHead1 == null && pTreeHead2 == null)
return true;
return hasSubTreeCore(pTreeHead1, pTreeHead2);
}

/****
* 递归判断两棵树是否能构成子树
* 
* @param pTreeHead1
* @param pTreeHead2
* @return
*/
public boolean hasSubTreeCore(TreeNode pTreeHead1, TreeNode pTreeHead2) {
boolean result = false;
if (pTreeHead1.val == pTreeHead2.val) {
result = DoesTree1HaveAllNodesOfTree2(pTreeHead1, pTreeHead2);
}

if (!result && pTreeHead1.left != null)
result = hasSubTreeCore(pTreeHead1.left, pTreeHead2);
if (!result && pTreeHead1.right != null)
result = hasSubTreeCore(pTreeHead1.right, pTreeHead2);
return result;

}

/***
* 判断根节点相同，左右节点能够构成子树 pTreeHead1.val == pTreehead2.val 判断根节点下的左右子树 能否构成子树关系
* 
* @param pTreeHead1
* @param pTreeHead2
* @return
*/
public boolean DoesTree1HaveAllNodesOfTree2(TreeNode pTreeHead1,
TreeNode pTreeHead2) {
if (pTreeHead2 == null)
return true;
if (pTreeHead1 == null)
return false;
if (pTreeHead1.val != pTreeHead2.val)
return false;

return DoesTree1HaveAllNodesOfTree2(pTreeHead1.left, pTreeHead2.left)
&& DoesTree1HaveAllNodesOfTree2(pTreeHead1.right,
pTreeHead2.right);
}

/***
* 构建二叉树结构
* 
* @param pre
* @param begin1
* @param end1
* @param in
* @param begin2
* @param end2
* @return
*/
public TreeNode reConstructBinaryTree(int[] pre, int begin1, int end1,
int[] in, int begin2, int end2) {
if (begin1 > end1 || begin2 > end2) {
return null;
}
int rootData = pre[begin1];
TreeNode head = new TreeNode(rootData);
int divider = findIndexInArray(in, rootData, begin2, end2);
if (divider != -1) {
int offset = divider - begin2 - 1;
TreeNode left = reConstructBinaryTree(pre, begin1 + 1, begin1 + 1
+ offset, in, begin2, begin2 + offset);
TreeNode right = reConstructBinaryTree(pre, begin1 + 2 + offset,
end1, in, divider + 1, end2);
head.left = left;
head.right = right;
}
return head;
}

public int findIndexInArray(int[] a, int x, int begin, int end) {
for (int i = begin; i <= end; i++) {
if (a[i] == x)
return i;
}
return -1;
}

// 后序遍历
public void Traverse(TreeNode n) {
if (n != null) {
Traverse(n.left);
Traverse(n.right);
System.out.print(n.val + ",");
}
}

public static void main(String[] args) {
int preOrder[] = { 5, 4, 8, 9, 6, 8, 9, 2 };
int inOrder[] = { 9, 8, 6, 4, 5, 9, 8, 2 };

int preOrder2[] = { 9 };
int inOrder2[] = { 9 };

HasSubTree subTree = new HasSubTree();
TreeNode parent = subTree.reConstructBinaryTree(preOrder, 0,
preOrder.length - 1, inOrder, 0, inOrder.length - 1);
TreeNode child = subTree.reConstructBinaryTree(preOrder2, 0,
preOrder2.length - 1, inOrder2, 0, inOrder2.length - 1);
System.out.println("A树的后序输出结果：");
subTree.Traverse(parent);
System.out.println();
System.out.println("B树的后序输出结果：");
subTree.Traverse(child);
System.out.println();
if (subTree.hasSubTree(parent, child)) {
System.out.println("B 是 A 的一棵子树");
} else {
System.out.println("B 不是 A 的一棵子树");
}
}

}

发表于 2016-01-18 13:31:52 回复(0)
更多回答
会呼吸旳痛头像 会呼吸旳痛 
class IdenticalTree {
public:
   //isSame递归验证A B树是否完全相等，有坑注意：
   //虽然题意说拓扑结构相同即可，但还是要验证 A->val == B->val

    bool isSame(TreeNode* A, TreeNode* B)
    {
        if(A==NULL && B==NULL)return true;
        else if(A==NULL || B==NULL) return false;
        else return (A->val == B->val) && isSame(A->left,B->left) && isSame(A->right,B->right);
    }
    //验证是否有子树和B相同
    bool chkIdentical(TreeNode* A, TreeNode* B) {
        // write code here
        bool flag=isSame(A,B);
        if(flag) return true;//相同返回true
        else//不同则比较B是否和A的左右子树
            {
            return ((A->left != NULL && chkIdentical(A->left,B)) ||
                    (A->right != NULL && chkIdentical(A->right,B)));
        }
    }
};

编辑于 2016-09-11 21:40:11 回复(0)
HelloWorldn头像 HelloWorldn
题意是错的，应当改为不但需要拓扑结构相同，而且对应节点的val也相同，我很怀疑出题人到底有没有理解拓扑结构的含义。
编辑于 2017-01-05 14:00:12 回复(5)
C/C++
字节招聘--免笔试--流程快头像 字节招聘--免笔试--流程快

递归，注意写递归时的退出情况。

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/

class IdenticalTree {
public:
    bool isSame(TreeNode* a,TreeNode* b){
        if(a == NULL && b == NULL) return true;
        if(a == NULL && b != NULL) return false;
        if(a != NULL && b == NULL) return false;
        if(a->val != b->val) return false;
        else if(a->val == b->val){
            return isSame(a->left,b->left) && isSame(a->right,b->right);
        }
        return true;
    }
    bool chkIdentical(TreeNode* A, TreeNode* B) {
        // write code here
        if(A==NULL) return false;
        if(isSame(A,B)) return true;
        else{
            return chkIdentical(A->left,B) || chkIdentical(A->right,B);
        }
    }
};
发表于 2017-11-06 14:41:38 回复(0)
C/C++
kakaan头像 kakaan
1、添加缺失的叶子节点，将树转换成满树，这样才能完整的表达树的结构
2、将树转换成字符串，用字符串中查找字串来完成（string的find） 
    void preOrder(TreeNode* t, string &s)
    {
    	if(t != NULL)
        {
            s += ('0'+t->val);
            preOrder(t->left,s);
            preOrder(t->right,s);
        }
        else
        {
            s += '#'; // 缺失的叶子节点
        }
    }
    
    bool chkIdentical(TreeNode* A, TreeNode* B) {
        if(A == NULL && B == NULL) return true;
        if(A&&B)
        {
            string sA,sB;
            preOrder(A,sA);
            preOrder(B,sB);
            if(sA.find(sB) != string::npos) return true;
        }
        
        return false;
    }

编辑于 2016-08-27 22:05:44 回复(0)
C/C++
nbgao头像 nbgao 
class IdenticalTree {
public:     bool Equal(TreeNode *A,TreeNode *B){         if(A==NULL && B==NULL)             return true;         else if(A==NULL || B==NULL)             return false;         else             return (A->val==B->val) && Equal(A->left,B->left) && Equal(A->right,B->right);     }
    bool chkIdentical(TreeNode* A, TreeNode* B) {
        if(Equal(A,B))
            return true;
        else
            return (A->left!=NULL && chkIdentical(A->left,B)) || (A->right!=NULL && chkIdentical(A->right,B));
    }
};

发表于 2017-11-19 00:27:02 回复(0)
C/C++
Fannie-帆头像 Fannie-帆 

	class IdenticalTree {





	public:





	bool chkIdentical(TreeNode* A, TreeNode* B) {





	// write code here





	if (A==NULL && B==NULL) return true;





	else if (A==NULL || B==NULL) return false;





	





	if(isIdentical(A, B)) return true;





	if(chkIdentical(A->left, B)) return true;





	if(chkIdentical(A->right, B)) return true;





	





	return false;





	}





	





	bool isIdentical(TreeNode* A, TreeNode* B){





	if (A==NULL && B==NULL) return true;





	else if (A==NULL || B==NULL) return false;





	if (A->val==B->val && isIdentical(A->left, B->left) && isIdentical(A->right, B->right)) return true;





	else return false;





	}





	};


一定要确保终止条件，否则A或B为NULL时，会无限递归下去。

编辑于 2017-04-01 11:24:36 回复(0)
qibofang头像 qibofang 
    bool chkIdentical(TreeNode* A, TreeNode* B) {
        // write code here
        if(B == NULL) return true;
        if(A == NULL) return false;
        if(JudgeTopo(A, B)) return true;
        if(chkIdentical(A->left, B))
            return true;
        if(chkIdentical(A->right, B))
            return true;
        return false;
    }
    bool JudgeTopo(TreeNode* A, TreeNode* B){
        if((A==NULL&&B) || (A&&B==NULL)) return false;
        if(A==NULL&&B==NULL) return true;
        return A->val==B->val&&JudgeTopo(A->left,B->left)&&JudgeTopo(A->right,B->right);
    }

发表于 2016-09-09 12:52:17 回复(0)
Euroking头像 Euroking
测试用例:
{1,1,1,#,1,1,#},{1,#,1}
对应输出应该为:
true
你的输出为:
false
求问为什么输出是true？
编辑于 2016-08-30 21:04:33 回复(1)
JustYoung头像 JustYoung
这题的测试用例没问题吗？
测试用例:
{1,2,3,4,5,6,7},{1}

对应输出应该为:

false

你的输出为:

true

这对应输出不应该为true吗？为什么是false？
发表于 2016-02-22 22:56:55 回复(6)
Shield_W头像 Shield_W 
public class IdenticalTree {
    public boolean chkIdentical(TreeNode A, TreeNode B) {
        if (A == null && B != null) {     //这句不能掉，否则可能会抛出空指针异常
            return false;
    	}
        if (isIdentical(A, B)) {
            return true;
        }
        if (chkIdentical(A.left, B)) {
            return true;
        } else if (chkIdentical(A.right, B)) {
            return true;
        }
        return false;
    }
    public boolean isIdentical(TreeNode A, TreeNode B) {
        if (A == null && B == null) {
            return true;
        }
        if (A == null || B == null) {
            return false;
        }
        return A.val == B.val && isIdentical(A.left, B.left) && isIdentical(A.right, B.right);
    }
}

发表于 2016-08-25 19:09:20 回复(0)
果～果头像 果～果
先将二叉树A和B以相同的遍历顺序各自存储到一维数组a和b。然后再去判断。
发表于 2016-03-03 11:14:01 回复(2)
C++
勇敢牛牛，不怕困难！头像 勇敢牛牛，不怕困难！ 
class IdenticalTree {
public:
  bool chkIdentical(TreeNode* A, TreeNode* B) {
    if (!A) return false;
    return isSameTree(A, B) 
        || chkIdentical(A->left, B) 
        || chkIdentical(A->right, B);
  }
  
private:
  bool isSameTree(TreeNode* A, TreeNode* B) {
    if (!A || !B) return A == B;
    return A->val == B->val
        && isSameTree(A->left, B->left)
        && isSameTree(A->right, B->right);
  }
};

发表于 2021-07-24 12:01:12 回复(0)
Python
lx的流星头像 lx的流星 
# -*- coding:utf-8 -*-

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class IdenticalTree:
    def chkIdentical(self, A, B):
        # write code here
        def find(A,B):
            if not A and not B:#都为叶节点时则为相同
                return True
            elif not A and B:#不同时为空则不同
                return False
            elif A and not B:
                return False
            else:#都不为空时就要比较左子树和右子树
                return find(A.left,B.left) and find(A.right,B.right)
        result=False
        if A and B:
            if A.val==B.val:
                result=find(A,B)
            if not result:
                result=self.chkIdentical(A.left,B) or self.chkIdentical(A.right,B)
        return result
参考的大佬的答案，做了一点修改
编辑于 2019-07-22 21:12:36 回复(0)
C/C++
孜孜要努力鸭头像 孜孜要努力鸭
/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
/*二叉树序列化后用KMP算法验证B树的序列化结果是否是A树序列化结果的子串。
时间复杂度为O(m+n)。*/
class IdenticalTree {
public:
    bool chkIdentical(TreeNode* A, TreeNode* B) {
        // write code here
        string str1 = serialPre(A);
        string str2 = serialPre(B);
        return getIndexOf(str1,str2) != -1;
    }
    string serialPre(TreeNode* A)
    {
        if(A == NULL)
           return "#!";
        string res = to_string(A -> val) + "!";
        res += serialPre(A -> left);
        res += serialPre(A -> right);
        return res;
    }
    int getIndexOf(string s,string m)
    {
        if(m.size() < 1 || s. size() < m.size())
            return -1;
        int si = 0,mi = 0;
        vector<int> next = getNext(m);
        while(si < s.size() && mi < m.size())
        {
            if(s[si] == m[mi])
            {
                si++;
                mi++;
            }
            else if(next[mi] == -1)
                si++;
            else
                mi = next[mi];
        }
        return mi == m.size() ? si - mi : -1;
    }
    vector<int> getNext(string m)
    {
        vector<int> next(m.size(),-1);
        if(m.size() <= 1)
            return next;
        next[1] = 0;
        int pos = 2,cn =  0;
        while(pos < next.size())
        {
            if(m[pos - 1] == m[cn])
                next[pos++] = ++cn;
            else if(cn > 0)
                cn = next[cn];
            else
                next[pos++] = 0;
        }
        return next;
    }
};
发表于 2019-02-09 11:54:02 回复(0)
Python
离疏头像 离疏 
# -*- coding:utf-8 -*-

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class IdenticalTree:
    def chkIdentical(self, A, B):
        ans = False
        if A and B:
            if A.val==B.val:
                ans = self.help(A,B)
            if not ans:#AB当前根节点不等时，判断A的左、右子树是否等于B
                ans = self.chkIdentical(A.left,B)
            if not ans:
                ans = self.chkIdentical(A.right,B)
        return ans
             
    def help(self,a,b):
        if not a and not b:#a,b都为空，则已到达叶节点，且结构相同，返回true
            return True
        elif (a and not b) or (b and not a):#一个为空一个不为空，则结构不同，返回false
            return False
        return self.help(a.left,b.left) and self.help(a.right,b.right)#都不为空时，分别比较左右子树结构是否相同

发表于 2018-10-07 13:17:14 回复(0)
ErgouJing头像 ErgouJing
黑人问号脸？

发表于 2018-09-01 09:53:44 回复(0)
C/C++
NB响当当头像 NB响当当

        这里提供一种思路，先把两棵树按照某种遍历方法转化为一维数组，然后看 B 树的转化结果是不是 A 树的子序列，如果是，那就是其子树。只要知道先序(或者后续)+中序就可以完全确定树。但是为了简化，我们可以把树的空节点也表示出来，这样就把两棵树转化成了满二叉树，这样就可以通过一次遍历完全得知这棵树的构建方法，在使用上述方法即可。
        例如：(层遍历){1 1 1 # 1 1 #}{1 # 1}。转化为对应树为(设-99为NULL){1 1 -99 1 -99 1 1 -99 -99 -99}{1 -99 1 -99 -99}，后一个数组明显是前一个的子数组，因此返回True。
        参考代码如下： 

class IdenticalTree {
    void getPrnt(TreeNode *tree, vector &vec)
    {
        if (tree == nullptr)
        {
            vec.push_back(-99);
            return;
        }
        vec.push_back(tree->val);
        getPrnt(tree->left, vec);
        getPrnt(tree->right, vec);
    }
public:
    bool chkIdentical(TreeNode* A, TreeNode* B) {
        bool flag = false;
        vector mainTree, subTree;
        getPrnt(A, mainTree), getPrnt(B, subTree);
        for (int i = 0; i < mainTree.size(); i++)
        {
            int ptr1 = i, ptr2 = 0;
            while (ptr1 < mainTree.size() && ptr2 < subTree.size())
            {
                if (mainTree[ptr1++] != subTree[ptr2++]) break;
            }
            if (ptr2 >= subTree.size() && 
                 mainTree[ptr1 - 1] == subTree[ptr2 - 1])
            {
                flag = !flag;
                break;
            }
        }
        return flag;
    }
};

编辑于 2018-06-20 14:00:08 回复(0)
rzk2头像 rzk2
    bool IsSame(TreeNode *n1,TreeNode *n2)
    {
        if(!n1&&!n2) return true;
        if(!n1||!n2) return false;
        return (n1->val==n2->val)&&IsSame(n1->left,n2->left)&&IsSame(n1->right,n2->right);
    }
    bool chkIdentical(TreeNode* A, TreeNode* B) {
        // write code here
        if(!A||!B) return false;
        return IsSame(A,B)||chkIdentical(A->left,B)||chkIdentical(A->right,B);
    }
发表于 2018-05-26 15:09:22 回复(0)
C/C++
蛟龙吐火球丰头像 蛟龙吐火球丰 
//跟单纯找子树不同，需要A树也同时访问到叶节点
class IdenticalTree {
public:
    bool core(TreeNode* cura,TreeNode* curb)
    {
        if(cura==nullptr&&curb==nullptr)
            return true;
        if(!cura||!curb)
            return false;

         return cura->val==curb->val&&core(cura->left,curb->left)&&core(cura->right,curb->right);

    }

    bool chkIdentical(TreeNode* A, TreeNode* B) {
        // write code here
       if(A==nullptr)
           return false;
       if(core(A,B))
           return true;
       return (chkIdentical(A->left,B))||(chkIdentical(A->right,B));
    }
};
发表于 2018-05-18 10:34:08 回复(0)
xinshouhuangfang头像 xinshouhuangfang 
/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/

class IdenticalTree {
public:
    string serialize(TreeNode*A){
        if(!A)return "#";
        char buf[256];
        snprintf(buf,sizeof(buf),"%d",A->val);
        return buf+serialize(A->left)+serialize(A->right);
    }
    bool chkIdentical(TreeNode* A, TreeNode* B) {
        string sA=serialize(A),sB=serialize(B);
        return sA.find(sB) != string::npos;
    }
};

发表于 2018-05-12 14:00:13 回复(0)
提交观点

问题信息

字符串 树 递归
难度：
35条回答 23436浏览

热门推荐

通过挑战的用户

查看代码

相关试题

拓扑结构相同子树

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号