Same Tree

Given two binary trees, write a function to check if they are equal or not.

Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

判断两棵树是否相同和之前的判断两棵树是否对称都是一样的原理，利用深度优先搜索DFS来递归: 如果根节点相同，再递归的看左子树和右子树是否相同

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

class Solution(object):
    def isSameTree(self, p, q):
        """
        :type p: TreeNode
        :type q: TreeNode
        :rtype: bool
        """
        if not p and not q:
            return True
        if not p and q:
            return False
        if not q and p:
            return False
        if p.val != q.val:
            return False
        return self.isSameTree(p.left,q.left) and self.isSameTree(p.right, q.right)

BFS(Queue)

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

class Solution(object):
    def isSameTree(self, p, q):
        """
        :type p: TreeNode
        :type q: TreeNode
        :rtype: bool
        """
        # BFS
        queue = [(p,q)]
        while queue:
            nodeP, nodeQ = queue.pop(0)
            if nodeP and nodeQ and nodeP.val == nodeQ.val:
                # 记得双括号
                queue.append((nodeP.left, nodeQ.left))
                queue.append((nodeP.right, nodeQ.right))
            elif not nodeP and not nodeQ:
                continue
            else:
                return False
        return True

DFS(Stack)

与bfs两点不同：

1. bfs用queue，pop(0)出list里第一个元素; dfs用stack， pop()出list最后一个元素

2. bfs 先加左子树，再加右子树；dfs先加右子树再加左子树

# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def isSameTree(self, p, q):
        """
        :type p: TreeNode
        :type q: TreeNode
        :rtype: bool
        """
        # DFS
        stack = [(p,q)]
        while stack:
            nodeP, nodeQ = stack.pop()
            if nodeP and nodeQ and nodeP.val == nodeQ.val:
                # 记得双括号
                stack.append((nodeP.right, nodeQ.right))
                stack.append((nodeP.left, nodeQ.left))
            elif not nodeP and not nodeQ:
                continue
            else:
                return False
        return True