面试题19. 二叉树的镜像

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

输入描述: 二叉树的镜像定义：

源二叉树镜像二叉树     8    / \    6 10   / \ / \  5 7 9 11     8    / \   10 6   / \ / \ 11 9 7 5

思路： 本题的考点是递归。 首先交换左右两个孩子结点，然后递归处理左子树和右子树

注意： 输入为null的情况； 只有一个根节点的情况； 树一边倒的情况（比如每个节点都只有左节点）

Java 代码如下：

/** 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; Mirror(root.left); Mirror(root.right); } }

Python代码如下：

# -*- coding:utf-8 -*- # 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 self.Mirror(root.left) self.Mirror(root.right) temp = root.left root.left = root.right root.right = temp return root