100. 相同的树

Difficulty
easy
Tags
二叉树
URL
https://leetcode-cn.com/problems/same-tree/
Star
给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
示例 1：
notion imagenotion image
输入：p = [1,2,3], q = [1,2,3]
输出：true
示例 2：
notion imagenotion image
输入：p = [1,2], q = [1,null,2]
输出：false
示例 3：
notion imagenotion image
输入：p = [1,2,1], q = [1,1,2]
输出：false
提示：
  • 两棵树上的节点数目都在范围 [0, 100] 内
  • 104 <= Node.val <= 104
通过次数207,488提交次数343,165

法1 迭代 + BFS

思路
层次遍历两颗二叉树
题解
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        if p is None and q is None:
            return True
        elif p is None or q is None:
            return False
        queue = []
        queue.append(p)
        queue.append(q)
        while len(queue) > 0:
            if len(queue) % 2 !=0:
                return False
            p_node = queue.pop(0)
            q_node = queue.pop(0)
            
            if p_node.val != q_node.val:
                return False
            if p_node.left is None and q_node.left is not None:
                return False
            if p_node.left is not None and q_node.left is None:
                return False
            if p_node.right is None and q_node.right is not None:
                return False
            if p_node.right is not None and q_node.right is None:
                return False
            if p_node.left and q_node.left:
                queue.append(p_node.left)
                queue.append(q_node.left)
            if p_node.right and q_node.right:
                queue.append(p_node.right)
                queue.append(q_node.right)
        return True

法2 迭代 + dfs

思路
前序遍历二叉树，遍历的时候判断
题解
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        if p is None and q is None:
            return True
        elif p is None or q is None:
            return False
        stack = []
        stack.append(p)
        stack.append(q)
        while len(stack) > 0:
            if len(stack) % 2 != 0:
                return False

            node_p = stack.pop()
            node_q = stack.pop()
            # 做判断
            if node_p.val != node_q.val:
                return False

            if node_p.left is None and node_q.left is None:
                pass
            elif node_p.left is None or node_q.left is None:
                return False
            
            if node_p.right is None and node_q.right is None:
                pass
            elif node_p.right is None or node_q.right is None:
                return False

            # 将子节点添加到stack
            if node_p.left:
                stack.append(node_p.left)
                stack.append(node_q.left)

            if node_q.right:
                stack.append(node_p.right)
                stack.append(node_q.right)
        return True

法3 递归

思路
先给递归函数下一个定义：
  • 参数： p q
  • 功能：返回p 子树和q子树是否相同
确定号函数定义后，描述基线条件，因为是判断两子树是否相同，所以找两子树最简单的情况（两子树高度不超过1）：
  • 两子树均为空，返回Tru
  • 只有一个为空，返回false
  • 均不空，查看节点值是否相同，不同返回False,相同就不用返回了，因为相同的话要向下一层做判断
题解
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        if p is None and q is None:
            return True
        elif p is None or q is None:
            return False
        elif p.val != q.val:
            return False
        
        return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)