判断两棵树是否相等

判断两棵树是否相等可以通过递归的方式实现。具体步骤如下：

1. 判断两个根节点是否相等，如果不相等则返回false，否则继续下一步。

2. 递归判断左子树和右子树是否相等，如果都相等则返回true，否则返回false。

以下是Java代码实现：

public boolean isSameTree(TreeNode p, TreeNode q) {
    if (p == null && q == null) { // 如果两个节点都为空，则相等
        return true;
    }
    if (p == null || q == null) { // 如果其中一个节点为空，则不相等
        return false;
    }
    if (p.val != q.val) { // 如果两个节点的值不相等，则不相等
        return false;
    }
    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right); // 递归判断左右子树是否相等
}

其中，TreeNode是一个树节点的类，包含了val、left、right三个属性，分别表示节点的值、左子树和右子树。

相关问题

以二叉链表作为二叉树的存储结构，判断两棵树是否相等

### 回答1：
判断两棵二叉树是否相等，可以按照以下步骤进行：

1. 判断两棵树的根节点是否相等，如果不相等，则两棵树不相等。

2. 如果两棵树的根节点相等，则递归地判断它们的左子树和右子树是否相等。

3. 如果两棵树的左子树和右子树都相等，则这两棵树相等。

在二叉链表作为二叉树的存储结构时，可以通过比较两棵树的根节点、左子树和右子树的指针来判断它们是否相等。具体实现可以参考以下代码：

typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

bool isSameTree(TreeNode* p, TreeNode* q) {
    if (p == NULL && q == NULL) {
        return true;
    }
    if (p == NULL || q == NULL) {
        return false;
    }
    if (p->val != q->val) {
        return false;
    }
    return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}

### 回答2：
以二叉链表作为二叉树的存储结构，判断两棵树是否相等，需要递归地比较两棵树的根节点、左子树和右子树是否相等。具体实现步骤如下：

1.判断两棵树的根节点是否相等。

2.如果两棵树的根节点相等，则继续递归比较它们的左子树和右子树是否相等。如果两棵树的左子树都为空，则它们的左子树相等；如果两棵树的左子树都不为空，则递归比较它们的左子树和右子树是否相等；如果两棵树的左子树一个为空一个不为空，则它们的左子树不相等。同样的，对于右子树也是如此。

3.如果两棵树的根节点不相等，则它们不相等。

代码实现如下：

bool isEqual(BiTreeNode *T1, BiTreeNode *T2) {
if(T1 == nullptr && T2 == nullptr) return true; //两棵树都为空，相等
if(T1 == nullptr || T2 == nullptr) return false; //两棵树只有一棵为空，不相等
if(T1->data != T2->data) return false; //两棵树的根节点不相等，不相等
return isEqual(T1->lchild, T2->lchild) && isEqual(T1->rchild, T2->rchild); //递归比较左子树和右子树是否相等
}

其中，BiTreeNode是二叉链表的节点类型，包括data（节点数据）、lchild（左子树指针）和rchild（右子树指针）。

使用以上算法，可以判断两棵树是否相等。它的时间复杂度为O(n)，其中n为树中节点数。

### 回答3：
如果以二叉链表作为二叉树的存储结构，判断两棵树是否相等时需要遵循以下原则：

1. 如果两棵树都为空，则两棵树相等；
2. 如果有一棵树为空，而另一棵树不为空，则两棵树不相等；
3. 如果两棵树的根节点的数据不同，则两棵树不相等；
4. 如果两棵树的根节点的数据相同，并且它们的左子树和右子树都相等，则两棵树相等。在比较左子树和右子树是否相等时，可以使用递归的方法。

具体实现过程如下：

1. 首先判断两棵树是否为空，如果都为空，则它们相等；
2. 如果有一棵树为空，而另一棵树不为空，则它们不相等；
3. 如果两棵树的根节点的数据不同，则它们不相等；
4. 如果两棵树的根节点的数据相同，我们需要递归地比较它们的左子树和右子树是否相等，如果都相等，则它们相等，否则它们不相等。

代码实现如下：

class TreeNode:
    def __init__(self, val=None, 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:
        return True
    # 如果有一棵树为空，而另一棵树不为空，则它们不相等
    if not p or not q:
        return False
    # 如果两棵树的根节点的数据不同，则它们不相等
    if p.val != q.val:
        return False
    # 递归比较左子树和右子树
    return isSameTree(p.left, q.left) and isSameTree(p.right, q.right)

综上，以二叉链表作为二叉树的存储结构，判断两棵树是否相等可以通过递归比较它们的根节点、左子树和右子树的方式实现。

以二叉链表作为二叉树的存储结构，编写以下算法： （1）统计二叉树的叶结点个数。 （2）判断两棵树是否相等。 （3）交换二叉树每个结点的左孩子和右孩子。

好的，我来回答您的问题。

（1） 统计二叉树的叶结点个数的算法如下：

def count_leaves(root):
    if not root:
        return 0
    if not root.left and not root.right:
        return 1
    return count_leaves(root.left) + count_leaves(root.right)

（2） 判断两棵树是否相等的算法如下：

def is_same_tree(p, q):
    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)

（3） 交换二叉树每个结点的左孩子和右孩子的算法如下：

def invert_tree(root):
    if not root:
        return None
    root.left, root.right = root.right, root.left
    invert_tree(root.left)
    invert_tree(root.right)
    return root

希望能够帮助到您！如果您有其他问题可以继续提问。