# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
‘‘‘
1.用一个栈来操作两棵树
2.每次入栈同时压入两棵树的节点
3.每次去除同时取出两棵树的节点，这样和操作一棵树是一样的。
‘‘‘
class Solution(object):
    def isSameTree(self, p, q):
        """
        :type p: TreeNode
        :type q: TreeNode
        :rtype: bool
        """
        if p is None and q is None:return True
        if p is None and q: return False
        if p and q is None :return False
        que = []
        que.append(p)
        que.append(q)
        while que:
            nodep = que.pop(0)
            nodeq = que.pop(0)
            #当前节点一定是存在的，只需要对比值是否相同就行
            if nodep.val!=nodeq.val:return False
                        
            #先是p,q的左子节点存在->入栈
            #(不管值对不对，这里只关心两棵树的子节点是否都存在，值的正确与否交给上一行代码)
            #然后列出两棵树的子节点不一致的情况（笨办法，全列出来了。。。因为有可能遇到叶子节点）           
            if nodep.left and nodeq.left:
                que.append(nodep.left)
                que.append(nodeq.left)
            elif nodep.left and nodeq.left is None:return False
            elif nodep.left is None and nodeq.left:return False
            if nodep.right and nodeq.right:
                que.append(nodep.right)
                que.append(nodeq.right)
            elif nodep.right and nodeq.right is None:return False
            elif nodep.right is None and nodeq.right : return False
        #全部没问题，返回True
        return True
            

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
‘‘‘
1.同样是用一个栈来遍历两棵树
‘‘‘
class Solution(object):
    def isSameTree(self, p, q):
        """
        :type p: TreeNode
        :type q: TreeNode
        :rtype: bool
        """

        sk = []
        sk.append(p)
        sk.append(q)
        while sk:
            nodep = sk.pop(0)
            nodeq = sk.pop(0)                            
            ‘‘‘
            两棵树的当前节点可能出现的几种情况
               p     q
            1.None，None （两个都为空）
            2. 3  ，None （一个不为空，一个空）
            3.None， 3   （一个空，一个不为空）
            4. 3  ， 2   （都不为空，但值不同）
            5. 3  ， 3   （正解）
            ‘‘‘
            #第一种情况
            if nodep is None and nodeq is None:
                continue
            ##因为排除了两个都为空的情况，就只剩下(情况2,情况3)、情况4、(正解)
            #因此(情况2,情况3)只需要判断其中一个是否为None                        
            if nodep is None or nodeq is None or nodep.val!=nodeq.val:
                return False
                                
            #因为是关注的当前节点，所以空子节点也会入栈
            sk.append(nodep.left)
            sk.append(nodeq.left)
            
            sk.append(nodep.right)
            sk.append(nodeq.right)
        return True