刷题14——面试题27：二叉树的镜像

题目：

请完成一个函数，输入一棵二叉树，该函数输出它的镜像。

如下图所示，即为两棵互为镜像的二叉树：

思路：

现在我们来仔细分析这两棵树的特点，总结出求镜像的步骤。这两颗树的根节点相同，但它们的左、右两个子节点交换了位置。因此，我们不妨先在树中交换根节点的两个子节点，得到下图的第二棵树。

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

注：（a）交换根节点的左、右子树；（b）交换值为10的节点的左、右子节点；（c）交换值为6的节点的左、右子节点

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

综上，python代码如下：

class TreeNode:
    def __init__(self, x):
        self.val =x
        self.left =None
        self.right =None
        
class Solution:
    def Mirror(self, root):
        if not root:
            return None
        root.left, root.right =root.right, root.left
        if root.left:
            self.Mirror(root.left)
        if root.right:
            self.Mirror(root.right)

java代码如下：

//二叉树结构定义如下
class BinaryTreeNode{
    public int value;
    public BinaryTreeNode leftNode;
    public BinaryTreeNode rightNode;
    
    public BinaryTreeNode(){
        
    }
    
    public BinaryTreeNode(int value){
        this.value =value;
        this.leftNode =null;
        this.rightNode =null;
    }
}

public class MirrorOfBinaryTree{
    public void Mirror(BinaryTreeNode node){
        if (node ==null)
            return;
        if (node.leftNode ==null && node.rightNode ==null)
            return;
        
        BinaryTreeNode temp =node.leftNode;
        node.leftNode =node.rightNode;
        node.rightNode =temp;
        if(node.leftNode != null)
            Mirror(node.leftNode);
        if(node.rightNode !=null)
            Mirror(node.rightNode);
    }
}

更多精彩，关注“咋家”

image