第 27 題：操作給定的二叉樹牢硅，將其變換為源二叉樹的鏡像
傳送門：二叉樹的鏡像，懦饧荆客網(wǎng) online judge 地址。
輸入一個(gè)二叉樹累驮，將它變換為它的鏡像酣倾。
樣例：
輸入樹：
8 / \ 6 10 / \ / \ 5 7 9 11
[8,6,10,5,7,9,11,null,null,null,null,null,null,null,null]
輸出樹：8 / \ 10 6 / \ / \ 11 9 7 5
[8,10,6,11,9,7,5,null,null,null,null,null,null,null,null]
分析：這道題的解決實(shí)際上考察了二叉樹的遍歷，事實(shí)上谤专，前序遍歷躁锡、后序遍歷、層序遍歷都是可以完成題目要求的置侍。
思路1：遞歸方式：前序遍歷或者后序遍歷都行映之。
Python 代碼：前序遍歷
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def mirror(self, root):
"""
:type root: TreeNode
:rtype: void
"""
# 先寫遞歸終止條件
if root is None:
return root
# 按照前序遍歷的方式
root.left, root.right = root.right, root.left
self.mirror(root.left)
self.mirror(root.right)
Java 代碼：
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);
}
public void Mirror1(TreeNode root) {
if (root == null) {
return;
}
Mirror(root.left);
Mirror(root.right);
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
}
}
Python 代碼：后序遍歷
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def mirror(self, root):
"""
:type root: TreeNode
:rtype: void
"""
# 先寫遞歸終止條件
if root is None:
return root
# 按照后序遍歷的方式
self.mirror(root.left)
self.mirror(root.right)
root.left, root.right = root.right, root.left
Python 代碼：層序遍歷
class Solution(object):
def mirror(self, root):
"""
:type root: TreeNode
:rtype: void
"""
# 先寫遞歸終止條件
if root is None:
return root
queue = [root]
while queue:
top = queue.pop(0)
top.left, top.right = top.right, top.left
if top.left:
queue.append(top.left)
if top.right:
queue.append(top.right)
return root
思路2：非遞歸方式（沒(méi)有看出來(lái)是那種遞歸方式）。
Java 代碼：
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);
}
public void Mirror1(TreeNode root) {
if (root == null) {
return;
}
Mirror(root.left);
Mirror(root.right);
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
}
}
非遞歸方式：下面這個(gè)代碼有點(diǎn)意思蜡坊。
Python 代碼：
class Solution:
def Mirror(self, root):
if root is None:
return
stack = []
while root or stack:
while root:
root.left, root.right = root.right, root.left
stack.append(root)
root = root.left
if stack:
root = stack.pop()
root = root.right
