拓扑结构相同子树

[编程题]拓扑结构相同子树

热度指数：4637 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

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

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

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

算法知识视频讲解

Python

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)

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)