深入理解反转二叉树

小蓝 • 2024-12-27 12:57 • 编程

二叉树是一种重要的数据结构，常用于搜索、排序、计算等领域。反转二叉树指将所有节点的左右子树交换，即对于原二叉树中的任意一个节点，如果其左子树不空，则交换左右子树，如果其右子树不为空，则交换左右子树。反转二叉树是一道经典的面试题，也是实际开发中常用到的技巧。

一、递归实现反转二叉树

将左右子树交换可以看成是对节点的一次操作，所以递归是一个自然的选择。递归方法的主要思路是对于根节点，先交换其左右子树，然后对左右子树分别递归调用反转函数。

public TreeNode invertTree(TreeNode root) {
    if (root == null) return null;
    TreeNode tmp = root.left;
    root.left = invertTree(root.right);
    root.right = invertTree(tmp);
    return root;
}

代码实现简单明了，先判断根节点是否为空，如果不为空，交换其左右子树，并分别递归调用其左右子节点。

二、迭代实现反转二叉树

递归实现的思路简单，但有可能会爆栈。为了避免这种情况发生，我们可以使用循环迭代的方法实现反转二叉树。迭代方法需要借助栈来实现，对于每一个节点，我们将其左右子节点交换后，将其放入栈中，然后从栈中取出节点并重复上述操作，直至栈为空。

public TreeNode invertTree(TreeNode root) {
    if (root == null) return null;
    Stack stack = new Stack();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        TreeNode tmp = node.left;
        node.left = node.right;
        node.right = tmp;
        if (node.left != null) stack.push(node.left);
        if (node.right != null) stack.push(node.right);
    }
    return root;
}

代码实现中，我们使用了标准的栈数据结构来存储每个节点，并依次取出节点。对于每个节点，交换左右子树，然后分别将左右子节点入栈。重复上述步骤，直至栈为空。

三、反转二叉树的应用

反转二叉树是一个简单而又实用的技巧，可以用于多种应用场景。以下是其中的两个例子：

1. 获取二叉树的镜像

二叉树的镜像是指以根节点为对称轴，交换其左右子树后得到的新二叉树。获取二叉树的镜像可以直接使用反转二叉树的方法实现。

TreeNode mirror(TreeNode root) {
    return invertTree(root);
}

2. 判断两个二叉树是否相同

判断两个二叉树是否相同，可以通过先将两个二叉树反转，然后依次比较它们的每个节点是否相同，即可得出结论。

public boolean isSameTree(TreeNode p, TreeNode q) {
    TreeNode t1 = invertTree(p);
    TreeNode t2 = invertTree(q);
    return isSame(t1, t2);
}
private boolean isSame(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 isSame(p.left, q.left) && isSame(p.right, q.right);
}

总结

通过本文，我们详细介绍了反转二叉树的实现方法以及其在实际应用中的作用。熟练掌握反转二叉树的方法可以帮助我们更好地理解二叉树的基本操作，提高我们的编程技巧。

原创文章，作者：小蓝，如若转载，请注明出处：https://www.506064.com/n/295941.html