相同二叉树 2020-05-07 wxx

leetcode100
相同的二叉树
给定两个二叉树，编写一个函数来检验它们是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

class Solution:

    # 利用层次遍历做，相对直观
    def isSameTree1(self, p: TreeNode, q: TreeNode) -> bool:
        
        p_list = list()
        q_list = list()
        p_list.append(p)
        q_list.append(q)
        not_same_flag = 0
        while len(p_list) == len(q_list) and len(p_list) != 0:
            for i in range(len(p_list)):
                Pop1 = p_list.pop(0)
                Pop2 = q_list.pop(0)
                # 取pop的值判断
                if Pop1 is not None and Pop2 is not None:
                    if Pop1.val == Pop2.val:
                        p_list.append(Pop1.left)
                        p_list.append(Pop1.right)
                        q_list.append(Pop2.left)
                        q_list.append(Pop2.right)
                    else:
                        not_same_flag = 1
                        break
                elif Pop1 is None and Pop2 is None:
                    pass
                else:
                    not_same_flag = 1
                    break
            if not_same_flag == 1:
                break
        return not_same_flag == 0

    # 递归写法（必须理解掌握）
    # 【树相同 = 根相同+ 左子树相同 + 右子树相同】
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        # 递归出口: p q 为None
        if p is None and q is None:
            return True
        
        # 只要p q有一个不为None，就做如下判断
        # p, q的val是否一致 + 左子树是否一致 + 右子树是否一致
        return (p and q and p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)) is True