本文共 1724 字，大约阅读时间需要 5 分钟。

二叉树及其相关问题

二叉树的遍历

在编程中，二叉树的遍历是常见操作之一。我们可以通过递归方法实现对二叉树的遍历。以下是一个示例函数：

void traverse(TreeNode root) {
    // 递归遍历二叉树
    if (root == null) {
        return;
    }
    traverse(root.left); // 先遍历左子树
    traverse(root.right); // 再遍历右子树
}

这个函数的作用是按前序方式（先左后右）遍历二叉树。根节点会先被访问，然后是其左子树，最后是右子树。

检查两棵二叉树是否是子树关系

我们可以通过递归的方法来判断两棵二叉树是否是子树关系。以下是实现思路：

以下是实现代码：

public boolean hasSubtree(TreeNode root1, TreeNode root2) {
    if (root2 == null) {
        return true; // 如果root2为空，root1也是子树
    }
    if (root1 == null) {
        return false; // root1为空，root2不可能是其子树
    }
    // 检查root2是否是root1的子树
    if (hasSubtree(root1, root2)) {
        return true;
    }
    // 检查root2是否在root1的左子树或右子树中
    return hasSubtree(root1.left, root2) || hasSubtree(root1.right, root2);
}
private boolean hasSubtree(TreeNode root1, TreeNode root2) {
    if (root1 == null && root2 == null) {
        return true; // 两个节点都为空，满足子树条件
    }
    if (root1 == null || root2 == null) {
        return false; // 至少有一个为空，不是子树
    }
    // 递归检查左子树和右子树
    return hasSubtree(root1.left, root2.left) && hasSubtree(root1.right, root2.right);
}

这个方法的时间复杂度为O(n1)，其中n1是较大二叉树的节点数。

二叉树的镜像

镜像二叉树意味着交换节点的左右子树。以下是实现思路：

以下是实现代码：

public TreeNode mirror(TreeNode pRoot) {
    if (pRoot == null) {
        return null;
    }
    // 交换左右节点
    TreeNode temp = pRoot.left;
    pRoot.left = pRoot.right;
    pRoot.right = temp;
    // 递归镜像左子树
    if (pRoot.left != null) {
        mirror(pRoot.left);
    }
    // 递归镜像右子树
    if (pRoot.right != null) {
        mirror(pRoot.right);
    }
    return pRoot;
}

通过这种方法，我们可以将给定的二叉树镜像反转。