这周一道算法题(六十七)

本周题目难度'Easy',使用语言'Python'。我做算法题也要比较长的时间，最近太忙了，不想鸽太多就挑了一道简单的。。。

题目：给你两个二叉树，让你判断是否相同(节点个树及节点具有相同的值)

思路：思路比较简单，就是一个节点一个节点的遍历对比呗，看代码(isSameTree)：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isSameTree(self, p, q):
        """
        :type p: TreeNode
        :type q: TreeNode
        :rtype: bool
        """
        # 我写了一个方法，来判断节点是否相同
        def isSameTreeNode(p, q):
            # 如果值不相同返回False
            if p.val != q.val:
                return False
            # 如果p的左子节点和q的左子节点都有值就继续遍历
            if p.left and q.left:
                if isSameTreeNode(p.left, q.left)== False:
                    return False
            # 否则如果只有一个节点有值就返回False
            elif p.left or q.left:
                return False
            # 如果p的右子节点和q的右子节点都有值就继续遍历
            if p.right and q.right:
                if isSameTreeNode(p.right, q.right) == False:
                    return False
            # 否则如果只有一个节点有值就返回False
            elif p.right or q.right:
                return False
        # 如果p和q不为空就去遍历节点
        if p and q:
            if isSameTreeNode(p, q) == False:
                return False
        # 否则p和q只有一个为空就返回False
        elif p or q:
            return False
        # 如果都OK就返回True啦
        return True

虽然做出来了，但效率很低，还是需要优化，看看效率高的：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isSameTree(self, p, q):
        """
        :type p: TreeNode
        :type q: TreeNode
        :rtype: bool
        """
        # 如果p和q都为空返回True
        if(p==None and q==None):
            return True
        # 有一个不为空返回False
        if(p==None):
            return False
        if(q==None):
            return False
        # 如果节点值相同就去遍历子节点（这个写的很妙）
        if(p.val==q.val):
            return self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right)
        # 节点值不相同就返回False
        else:
            return False

活到老学到老，共同学习，共同提高。。。

版权声明：本文为 Crazy Steven 原创出品，欢迎转载，转载时请注明出处!