剑指Offer面试题：18.二叉树的镜像
一、题目：二叉树的镜像
题目：请完成一个函数，输入一个二叉树，该函数输出它的镜像。例如下图所示，左图是原二叉树，而右图则是该二叉树的镜像。
该二叉树节点的定义如下，采用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 > 0) { 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 > 0) { 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(8); BinaryTreeNode node2 = new BinaryTreeNode(6); BinaryTreeNode node3 = new BinaryTreeNode(10); BinaryTreeNode node4 = new BinaryTreeNode(5); BinaryTreeNode node5 = new BinaryTreeNode(7); BinaryTreeNode node6 = new BinaryTreeNode(9); BinaryTreeNode node7 = new BinaryTreeNode(11); SetSubTreeNode(node1, node2, node3); SetSubTreeNode(node2, node4, node5); SetSubTreeNode(node3, node6, node7); BinaryTreeHelper.SetMirrorIteratively(node1); string completed = GetNodeString(node1); Assert.AreEqual(completed,"810611975"); } // 02.测试二叉树：出叶子结点之外，左右的结点都有且只有一个左子结点 // 8 // 7 // 6 // 5 // 4 [TestMethod] public void MirrorTest2() { BinaryTreeNode node1 = new BinaryTreeNode(8); BinaryTreeNode node2 = new BinaryTreeNode(7); BinaryTreeNode node3 = new BinaryTreeNode(6); BinaryTreeNode node4 = new BinaryTreeNode(5); BinaryTreeNode node5 = new BinaryTreeNode(4); node1.leftChild = node2; node2.leftChild = node3; node3.leftChild = node4; node4.leftChild = node5; BinaryTreeHelper.SetMirrorIteratively(node1); string completed = GetNodeString(node1); Assert.AreEqual(completed, "87654"); } // 03.测试二叉树：出叶子结点之外，左右的结点都有且只有一个右子结点 // 8 // 7 // 6 // 5 // 4 [TestMethod] public void MirrorTest3() { BinaryTreeNode node1 = new BinaryTreeNode(8); BinaryTreeNode node2 = new BinaryTreeNode(7); BinaryTreeNode node3 = new BinaryTreeNode(6); BinaryTreeNode node4 = new BinaryTreeNode(5); BinaryTreeNode node5 = new BinaryTreeNode(4); node1.rightChild = node2; node2.rightChild = node3; node3.rightChild = node4; node4.rightChild = node5; BinaryTreeHelper.SetMirrorIteratively(node1); string completed = GetNodeString(node1); Assert.AreEqual(completed, "87654"); }
3.2 特殊输入测试
// 04.测试只有一个结点的二叉树 // 8 [TestMethod] public void MirrorTest4() { BinaryTreeNode node1 = new BinaryTreeNode(8); BinaryTreeHelper.SetMirrorIteratively(node1); string completed = GetNodeString(node1); Assert.AreEqual(completed, "8"); } // 05.测试空二叉树：根结点为空指针 [TestMethod] public void MirrorTest5() { BinaryTreeNode node1 = null; BinaryTreeHelper.SetMirrorIteratively(node1); string completed = GetNodeString(node1); Assert.AreEqual(completed, null); }
3.3 测试结果
（1）测试通过情况
（2）代码覆盖率
正文到此结束
