LeetCode: 100 Same Tree

•

admin

Given the roots of two binary trees p and q, write a function to check if they are the same or not.

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

Example:

Input: p = [1,2,3], q = [1,2,3]
Output: true

Example:

Input: p = [1,2], q = [1,null,2]
Output: false

Example:

Input: p = [1,2,1], q = [1,1,2]
Output: false

问题

给定两个二叉树的根节点 p 和 q，编写一个函数来检查它们是否相同。

如果两个二叉树在结构上完全相同，并且节点具有相同的值，则认为它们是相同的。

解决方案 1

递归法

Approach 1 / 方法 1

This solution uses a recursive approach to compare the two binary trees. The idea is to traverse both trees simultaneously and compare the corresponding nodes. If both nodes are None, they are considered the same. If both nodes have the same value and their respective left and right children are also the same, the trees are identical.

该解决方案使用递归方法来比较两个二叉树。其思想是同时遍历两棵树并比较相应的节点。如果两个节点都是 None，则认为它们是相同的。如果两个节点具有相同的值，并且它们各自的左右子节点也相同，则这两棵树是相同的。

Implementation / 实现

python

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 not p and not q:
            return True
        if not p or not q:
            return False
        if p.val != q.val:
            return False

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

Explanation / 解释

  1. Base Case: Both Nodes are None / 基本情况：两个节点都是 None

    if not p and not q:
   return True
    • English: If both p and q are None, the trees are considered the same at this point, so we return True.
    • Chinese: 如果 p 和 q 都为 None，则此时认为这两棵树是相同的，因此我们返回 True。

  2. Check if One Node is None / 检查一个节点是否为 None

    if not p or not q:
   return False
    • English: If one of the nodes is None and the other is not, the trees are not the same, so we return False.
    • Chinese: 如果一个节点为 None，而另一个节点不为 None，则这两棵树不同，因此我们返回 False。

  3. Compare the Values of p and q / 比较 p 和 q 的值

    if p.val != q.val:
   return False
    • English: If the values of p and q are not equal, the trees are not the same, so we return False.
    • Chinese: 如果 p 和 q 的值不相等，则这两棵树不同，因此我们返回 False。

  4. Recursively Check Left and Right Subtrees / 递归检查左右子树

    return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
    • English: We recursively check if the left subtrees of p and q are the same and if the right subtrees of p and q are the same. If both are true, the trees are identical.
    • Chinese: 我们递归地检查 p 和 q 的左子树是否相同，以及 p 和 q 的右子树是否相同。如果两者都为真，则这两棵树是相同的。

Complexity Analysis / 复杂度分析

  • Time Complexity / 时间复杂度: O(n), where n is the number of nodes in the trees. We visit each node exactly once.
  • Space Complexity / 空间复杂度: O(h), where h is the height of the trees. This space is used by the recursion stack.

Key Concept / 关键概念

  • Recursive Tree Comparison / 递归树比较: The recursive approach efficiently compares two binary trees by checking each corresponding node and its children.
  • 递归树比较: 递归方法通过检查每个对应的节点及其子节点，高效地比较两棵二叉树。

解决方案 2

迭代法（广度优先搜索）

Approach 2 / 方法 2

This solution uses an iterative approach with a queue to compare the two binary trees. The idea is to use breadth-first search (BFS) to traverse both trees level by level, comparing corresponding nodes.

该解决方案使用队列的迭代方法来比较两个二叉树。其思想是使用广度优先搜索（BFS）逐层遍历两棵树，比较相应的节点。

Implementation / 实现

python

from collections import deque

class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        queue = deque([(p, q)])

        while queue:
            node1, node2 = queue.popleft()

            if not node1 and not node2:
                continue
            if not node1 or not node2:
                return False
            if node1.val != node2.val:
                return False

            queue.append((node1.left, node2.left))
            queue.append((node1.right, node2.right))

        return True

Explanation / 解释

  1. Initialize a Queue / 初始化队列

    queue = deque([(p, q)])
    • English: We initialize a queue and enqueue a tuple containing the roots of both trees, p and q.
    • Chinese: 我们初始化一个队列，并将包含两棵树根节点 p 和 q 的元组加入队列。

  2. Iterate While the Queue is Not Empty / 在队列不为空时进行迭代

    while queue:
    • English: We enter a loop that continues as long as the queue is not empty.
    • Chinese: 我们进入一个循环，只要队列不为空，循环就会继续。

  3. Dequeue the Front Pair of Nodes / 从队列前端出列一对节点

    node1, node2 = queue.popleft()
    • English: We dequeue the front pair of nodes from the queue and assign them to node1 and node2.
    • Chinese: 我们从队列前端出列一对节点，并将它们分别赋值给 node1 和 node2。

  4. Check if Both Nodes are None / 检查两个节点是否都为 None

    if not node1 and not node2:
   continue
    • English: If both node1 and node2 are None, we continue to the next iteration since they are considered the same.
    • Chinese: 如果 node1 和 node2 都为 None，我们继续下一次迭代，因为它们被认为是相同的。

  5. Check if One Node is None / 检查一个节点是否为 None

    if not node1 or not node2:
   return False
    • English: If one node is None and the other is not, the trees are not the same, so we return False.
    • Chinese: 如果一个节点为 None，另一个节点不为 None，则这两棵树不同，因此我们返回 False。

  6. Compare the Values of node1 and node2 / 比较 node1 和 node2 的值

    if node1.val != node2.val:
   return False
    • English: If the values of node1 and node2 are not equal, the trees are not the same, so we return False.
    • Chinese: 如果 `node1

和 node2 的值不相等，则这两棵树不同，因此我们返回 False`。

  1. Enqueue the Left and Right Children / 将左子节点和右子节点加入队列

    queue.append((node1.left, node2.left))
queue.append((node1.right, node2.right))
    • English: We enqueue the left children of node1 and node2 as a pair, and the right children of node1 and node2 as another pair.
    • Chinese: 我们将 node1 和 node2 的左子节点作为一对加入队列，并将 node1 和 node2 的右子节点作为另一对加入队列。

  2. Return True If All Nodes Match / 如果所有节点匹配，返回 True

    return True
    • English: If we finish the loop without finding any mismatches, the trees are the same, so we return True.
    • Chinese: 如果我们完成循环后没有发现任何不匹配，则这两棵树是相同的，因此我们返回 True。

Complexity Analysis / 复杂度分析

  • Time Complexity / 时间复杂度: O(n), where n is the number of nodes in the trees. We visit each node exactly once.
  • Space Complexity / 空间复杂度: O(n), where n is the number of nodes in the trees. This space is used by the queue.

Key Concept / 关键概念

  • Breadth-First Search (BFS) / 广度优先搜索（BFS）: The iterative BFS approach efficiently compares two binary trees level by level, ensuring that corresponding nodes match.
  • 广度优先搜索（BFS）: 迭代的 BFS 方法通过逐层比较两个二叉树，确保相应的节点匹配。

Comparison / 比较

  1. Efficiency / 效率:

    • Recursive Approach / 递归方法: More space-efficient for balanced trees due to the smaller depth, but it can lead to stack overflow for very deep trees.
    • Iterative Approach (BFS) / 迭代方法（BFS）: Uses more memory in general due to the queue, but avoids the risk of stack overflow.

  2. Use Case / 使用场景:

    • Recursive / 递归: Preferred for simpler, smaller trees where recursion is straightforward and memory limitations are not a concern.
    • Iterative (BFS) / 迭代（BFS）: Preferred for larger trees or when you want to avoid the risk of recursion depth issues.

Summary / 总结

  • English: Both the recursive and iterative approaches are valid for determining if two binary trees are the same. The recursive method is more straightforward, while the iterative BFS method is more robust against deep recursion.
  • Chinese: 递归和迭代方法都可以有效地确定两棵二叉树是否相同。递归方法更直接，而迭代的 BFS 方法在深度递归方面更稳健。

Tips / 提示

  • English: Use the recursive approach for smaller trees and the iterative BFS approach for larger trees or when working with data structures where recursion might be limited.
  • Chinese: 对于较小的树，使用递归方法；对于较大的树或递归可能受限的数据结构，使用迭代的 BFS 方法。

Solution Template for Similar Questions / 提示

  • English: For problems involving tree comparison or traversal, both recursive and iterative approaches can be useful depending on the tree’s size and depth.
  • Chinese: 对于涉及树比较或遍历的问题，根据树的大小和深度，递归和迭代方法都可能有用。

5 More Similar Questions / 推荐5问题

  1. LeetCode 101. Symmetric Tree
  2. LeetCode 572. Subtree of Another Tree
  3. LeetCode 110. Balanced Binary Tree
  4. LeetCode 226. Invert Binary Tree
  5. LeetCode 654. Maximum Binary Tree

Recommended Resources / 推荐资源

  • English: Practice comparing binary trees using both recursive and iterative methods to strengthen your understanding of tree structures.
  • Chinese: 通过递归和迭代方法练习比较二叉树，以加深对树结构的理解。

Same Tree – Leetcode 100 – Python by NeetCode

Post Views: 21
, , ,

•

Comments

Leave a Reply

Your email address will not be published. Required fields are marked *