一、题目：二叉树的镜像
题目：请完成一个函数，输入一个二叉树，该函数输出它的镜像。例如下图所示，左图是原二叉树，而右图则是该二叉树的镜像。
该二叉树节点的定义如下，采用C#语言描述：
public class BinaryTreeNode
{
public int Data { get; set; }
public BinaryTreeNode leftChild { get; set; }
public BinaryTreeNode rightChild { get; set; } public BinaryTreeNode(int data)
{
this.Data = data;
} public BinaryTreeNode(int data, BinaryTreeNode left, BinaryTreeNode right)
{
this.Data = data;
this.leftChild = left;
this.rightChild = right;
}
}
二、解题思路
2.1 核心步骤
Step1.先序遍历原二叉树的每个节点，如果遍历到的结点有子结点，就交换它的两个子结点。
Step2.递归遍历每个节点的子节点，同样，如果遍历到的子节点有子节点，就交换它的两个子节点。
当交换完所有非叶子结点的左右子结点之后，就得到了树的镜像。下图展示了求二叉树的镜像的过程：
2.2 代码实现
（1）递归版实现
public static void SetMirrorRecursively(BinaryTreeNode root)
{
if (root == null || (root.leftChild == null && root.rightChild == null))
{
return;
} BinaryTreeNode tempNode = root.leftChild;
root.leftChild = root.rightChild;
root.rightChild = tempNode; if (root.leftChild != null)
{
// 递归调整左子树为镜像
SetMirrorRecursively(root.leftChild);
} if (root.rightChild != null)
{
// 递归调整右子树为镜像
SetMirrorRecursively(root.rightChild);
}
}
（2）循环版实现
public static void SetMirrorIteratively(BinaryTreeNode root)
{
if (root == null)
{
return;
} Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();
stack.Push(root); while (stack.Count > )
{
BinaryTreeNode node = stack.Pop(); BinaryTreeNode temp = node.leftChild;
node.leftChild = node.rightChild;
node.rightChild = temp; if (node.leftChild != null)
{
stack.Push(node.leftChild);
} if (node.rightChild != null)
{
stack.Push(node.rightChild);
}
}
}
三、单元测试
为了便于测试，封装了两个辅助方法，设置孩子节点和生成层次遍历的字符串：
/// <summary>
/// 辅助方法：设置root的lChild与rChild
/// </summary>
public void SetSubTreeNode(BinaryTreeNode root, BinaryTreeNode lChild, BinaryTreeNode rChild)
{
if (root == null)
{
return;
} root.leftChild = lChild;
root.rightChild = rChild;
} /// <summary>
/// 辅助方法：生成二叉树元素的字符串用于对比
/// </summary>
public string GetNodeString(BinaryTreeNode root)
{
if (root == null)
{
return null;
} StringBuilder sbResult = new StringBuilder(); Queue<BinaryTreeNode> queueNodes = new Queue<BinaryTreeNode>();
queueNodes.Enqueue(root);
BinaryTreeNode tempNode = null;
// 利用队列先进先出的特性存储节点并输出
while (queueNodes.Count > )
{
tempNode = queueNodes.Dequeue();
sbResult.Append(tempNode.Data); if (tempNode.leftChild != null)
{
queueNodes.Enqueue(tempNode.leftChild);
} if (tempNode.rightChild != null)
{
queueNodes.Enqueue(tempNode.rightChild);
}
} return sbResult.ToString();
}
3.1 功能测试
// 01.测试完全二叉树：除了叶子节点，其他节点都有两个子节点
// 8
// 6 10
// 5 7 9 11
[TestMethod]
public void MirrorTest1()
{
BinaryTreeNode node1 = new BinaryTreeNode();
BinaryTreeNode node2 = new BinaryTreeNode();
BinaryTreeNode node3 = new BinaryTreeNode();
BinaryTreeNode node4 = new BinaryTreeNode();
BinaryTreeNode node5 = new BinaryTreeNode();
BinaryTreeNode node6 = new BinaryTreeNode();
BinaryTreeNode node7 = new BinaryTreeNode(); SetSubTreeNode(node1, node2, node3);
SetSubTreeNode(node2, node4, node5);
SetSubTreeNode(node3, node6, node7); BinaryTreeHelper.SetMirrorIteratively(node1);
string completed = GetNodeString(node1);
Assert.AreEqual(completed,"");
} // 02.测试二叉树：出叶子结点之外，左右的结点都有且只有一个左子结点
// 8
// 7
// 6
// 5
//
[TestMethod]
public void MirrorTest2()
{
BinaryTreeNode node1 = new BinaryTreeNode();
BinaryTreeNode node2 = new BinaryTreeNode();
BinaryTreeNode node3 = new BinaryTreeNode();
BinaryTreeNode node4 = new BinaryTreeNode();
BinaryTreeNode node5 = new BinaryTreeNode(); node1.leftChild = node2;
node2.leftChild = node3;
node3.leftChild = node4;
node4.leftChild = node5; BinaryTreeHelper.SetMirrorIteratively(node1);
string completed = GetNodeString(node1);
Assert.AreEqual(completed, "");
} // 03.测试二叉树：出叶子结点之外，左右的结点都有且只有一个右子结点
// 8
// 7
// 6
// 5
// 4
[TestMethod]
public void MirrorTest3()
{
BinaryTreeNode node1 = new BinaryTreeNode();
BinaryTreeNode node2 = new BinaryTreeNode();
BinaryTreeNode node3 = new BinaryTreeNode();
BinaryTreeNode node4 = new BinaryTreeNode();
BinaryTreeNode node5 = new BinaryTreeNode(); node1.rightChild = node2;
node2.rightChild = node3;
node3.rightChild = node4;
node4.rightChild = node5; BinaryTreeHelper.SetMirrorIteratively(node1);
string completed = GetNodeString(node1);
Assert.AreEqual(completed, "");
}
3.2 特殊输入测试
// 04.测试只有一个结点的二叉树
//
[TestMethod]
public void MirrorTest4()
{
BinaryTreeNode node1 = new BinaryTreeNode(); BinaryTreeHelper.SetMirrorIteratively(node1);
string completed = GetNodeString(node1);
Assert.AreEqual(completed, "");
} // 05.测试空二叉树：根结点为空指针
[TestMethod]
public void MirrorTest5()
{
BinaryTreeNode node1 = null;
BinaryTreeHelper.SetMirrorIteratively(node1);
string completed = GetNodeString(node1);
Assert.AreEqual(completed, null);
}
3.3 测试结果
（1）测试通过情况
（2）代码覆盖率
