数据结构用递归方式判断两个二叉树是否相等的完整代码

数据结构中的二叉树相等判定通常通过递归方法完成，主要是比较每个节点的值以及左右子树是否对称。以下是使用Python语言的一个基本示例：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def isSameTree(p: TreeNode, q: TreeNode) -> bool:
    if not p and not q:  # 如果都是空节点，返回True
        return True
    elif not p or not q:  # 如果只有一个为空，返回False
        return False
    else:  # 否则，比较当前节点的值，再递归检查左右子树
        return p.val == q.val and isSameTree(p.left, q.left) and isSameTree(p.right, q.right)

这个函数`isSameTree`接受两个二叉树的根节点作为输入，如果它们的结构完全相同并且节点值匹配，则返回`True`，否则返回`False`。

相关问题

数据结构用递归方式判断两个二叉树是否相等

数据结构中，递归是一种常用的方法来比较两个二叉树是否相等。判断两个二叉树是否相等，通常需要对每个节点进行深度优先搜索，并检查以下条件：
1. 如果两个节点都为空，则它们是相等的。
2. 如果两个节点都不空，则它们需要同时满足以下条件：
- 节点的值相等。
- 左子树通过递归调用对比也相等。
- 右子树通过递归调用对比也相等。

以下是递归算法的基本思路：

def isSameTree(p, q):
    if p is None and q is None:
        return True
    elif p is None or q is None:
        return False
    else:
        return (p.val == q.val) and \
               isSameTree(p.left, q.left) and \
               isSameTree(p.right, q.right)

在这个函数中，`p` 和 `q` 分别代表两个二叉树的根节点。如果它们的当前节点值相等，且左右子树经过递归调用也分别相等，那么这两个二叉树就被认为是相等的。

数据结构判断两颗二叉树是否相等

判断两颗二叉树是否相等，需要比较它们的结构和节点值是否完全一致。

可以通过递归的方式，从根节点开始比较每个节点的值是否相等，以及左右子树是否相同。如果都相等，则说明两颗二叉树相等。

这个递归过程可以这样实现：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def is_same_tree(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 is_same_tree(p.left, q.left) and is_same_tree(p.right, q.right)

在这个实现中，首先判断两个节点是否为空，如果都为空，则说明已经比较到了叶子节点，返回 True。如果其中一个节点为空，另一个节点不为空，则说明两个节点不相等，返回 False。如果两个节点都不为空，则比较它们的值是否相等，以及它们的左右子树是否相等，如果都相等，则返回 True，否则返回 False。

这个算法的时间复杂度是 O(n)，其中 n 是二叉树中节点的个数，因为需要遍历每个节点进行比较。