二叉树的镜像

Love The Way You Lie 2022-05-14 04:13 181阅读 0赞

## 题目描述 ##

操作给定的二叉树，将其变换为源二叉树的镜像。

## 输入描述: ##

二叉树的镜像定义：
              源二叉树               镜像二叉树
        	    8                      8 
        	   /  \                   / \ 
        	  6   10                 10  6 
        	 / \  / \               / \ / \ 
        	5  7 9 11              11 9 7  5

二叉树的镜像就是二叉树的任一节点的左右子树都和与它互为镜像的二叉树对应节点的左右子树相反。

那么怎么求二叉树的镜像呢？

仔细分析上面两棵树的特点，这两棵树的根节点相同，但他们的左右两个子节点交换了位置。因此，我们不防先在树中交换根节点的两个子节点，就得到下图中的第二棵树。

交换根节点的两个子节点之后，我们注意到值为10、6的节点的子节点依然保持不变，因此我们还需要交换这两个子节点的左右子节点。交换之后的记过分别是下图中的第三棵树和第四棵树。做完这两次交换之后，我们已经便利玩所有的非叶节点。此时变换之后的树刚好就是原始树的镜像。

![70][]

上图求二叉树镜像的过程

（a）交换根节点的左、右子树；

（b）交换值为10的节点的左、右子节点；

（c）交换值为6的节点的左、右子节点。

总结上面的过程，我们得出求一棵树的镜像的过程：先前序遍历这棵树的每个节点，如果遍历到的节点有子节点，就交换它的两个子节点。当交换完所有的非叶节点的左、右子节点之后，就得到了树的镜像。

想清楚了解决这个问题的思路，我们就可以动手写代码了。

其中使用到的二叉树的数据结构如下：

public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
    
        public TreeNode(int val) {
            this.val = val;
        }
    
    }

**方法一**使用递归求二叉树的镜像：

public class Solution {
        public void Mirror(TreeNode root) {
            if(root == null){
                 return;
             }
             TreeNode temp = root.left;
             root.left = root.right;
             root.right = temp;
             if(root.left!=null){
                 Mirror(root.left);
             }
             if(root.right!=null){
                Mirror(root.right);
              } 
        }
    }

在该算法中，如果二叉树中有n个节点，那么该算法的时间复杂度为**O(n)**。

上面的代码是用递归实现的。如果要求用循环，则该如何实现?

可以使用循环压栈实现二叉树镜像，在压入节点的过程中交换节点的左右子树。

**方法二**使用循环求二叉树的镜像：

import java.util.Stack;
    public class Solution {
        public void Mirror(TreeNode root) {
            Stack stack = new Stack();
            if(root == null){
                return;
            }
            stack.push(root);
            while(stack.size() > 0) {
                TreeNode parent = (TreeNode) stack.peek();
                stack.pop();
                TreeNode temp = parent.left;
                parent.left = parent.right;
                parent.right = temp;
                if (parent.left != null) {
                    stack.push(parent.left);
                }
                if (parent.right != null) {
                    stack.push(parent.right);
                }
            }
        }
    }

该算法的思想和递归的思想是一样的，只不过使用栈模拟了递归调用的过程。

在该算法中，如果二叉树中有n个节点，那么该算法的时间复杂度也为**O(n)，但是占用了额外的空间用于存放节点，因此该算法的空间复杂度为O(n)。**

[70]: /images/20220514/46f10d6ebf414e328849a3685e0d7cd2.png