纵有疾风起
人生不言弃

剑指Offer面试题:18.二叉树的镜像


一、题目:二叉树的镜像

题目:请完成一个函数,输入一个二叉树,该函数输出它的镜像。例如下图所示,左图是原二叉树,而右图则是该二叉树的镜像。

剑指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.递归遍历每个节点的子节点,同样,如果遍历到的子节点有子节点,就交换它的两个子节点。

  当交换完所有非叶子结点的左右子结点之后,就得到了树的镜像。下图展示了求二叉树的镜像的过程:

剑指Offer面试题:18.二叉树的镜像插图(1)

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);            }        }    }

三、单元测试

  为了便于测试,封装了两个辅助方法,设置孩子节点和生成层次遍历的字符串:

剑指Offer面试题:18.二叉树的镜像插图(2)

    /// <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();    } 

View Code

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)测试通过情况

剑指Offer面试题:18.二叉树的镜像插图(4)

  (2)代码覆盖率

剑指Offer面试题:18.二叉树的镜像插图(5)

 

文章转载于:https://www.cnblogs.com/edisonchou/p/4774626.html

原著是一个有趣的人,若有侵权,请通知删除

未经允许不得转载:起风网 » 剑指Offer面试题:18.二叉树的镜像

分享到: 生成海报
avatar

评论 抢沙发

评论前必须登录!

立即登录   注册

切换注册

登录

忘记密码 ?

切换登录

注册

我们将发送一封验证邮件至你的邮箱, 请正确填写以完成账号注册和激活