21相同的树

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

示例 1:
1      1
/ \      / \
2 3      2 3
[1,2,3], [1,2,3]
输出: true

示例 2:
1      1
/       \
2      2
[1,2], [1,null,2]
输出: false

示例 3:
1      1
/\       /\
2 1      1 2
[1,2,1], [1,1,2]
输出: false

先序遍历

class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        def preorder(root):
            if not root:
                return [None]
            else:
                return [root.val] +preorder(root.left)+preorder(root.right)
        return preorder(p)==preorder(q)

递归判断

class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        if not p and not q:
            return True
        elif p and q:
            return p.val == q.val and self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right)
        else:
            return False

迭代

class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        stack = [(q, p)]
        while stack:
            a, b = stack.pop()
            if not a and not b:
                continue
            if a and b and a.val == b.val:
                stack.append((a.left, b.left))
                stack.append((a.right,b.right))
            else:
                return False
        return True

class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        if p == None and q == None:
            return True
        # 前提条件是两个节点不同时为空
        if p == None or q == None:
            return False
        # 中间发现值不相等，也不为空
        if p.val != q.val:
            return False

        return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

来源：力扣（LeetCode）