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

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

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)代码覆盖率

作者:周旭龙

出处:http://edisonchou.cnblogs.com

本文版权归作者和博客园共有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文链接。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 剑指Offer面试题:17.树的子结构

      为了方便测试,这里封装了一个设置指定根节点的左孩子和右孩子节点的方法:SetSubTreeNode

    Edison Zhou
  • 剑指Offer面试题:21.从上到下打印二叉树

      每一次打印一个结点的时候,如果该结点有子结点,则把该结点的子结点放到一个队列的末尾。接下来到队列的头部取出最早进入队列的结点,重复前面的打印操作,直至队列中...

    Edison Zhou
  • 剑指Offer面试题:23.二叉树中和为某一值的路径

      (1)当用前序遍历的方式访问到某一结点时,我们把该结点添加到路径上,并累加该结点的值。

    Edison Zhou
  • 着眼网络建设基础,华为的VR野心不是只有软硬件

    VRPinea
  • Vue[0x03] - Vue基础实践

    抓重点讲吧,最开始可追溯的版本号是0.6.0这个,但是正式对外发布的版本是在2014年1月24日发布的0.8.0。后面就是两个打头的里程碑,一个是1.x.x,一...

    丰臣正一
  • ExtJs一(Hello World)

      本文原文链接地址 http://aehyok.com/Blog/Detail/48.html

    aehyok
  • ExtJs一(Hello World)

      本文原文链接地址 http://aehyok.com/Blog/Detail/48.html

    aehyok
  • 01布尔模型&倒排索引

    原文链接: http://www.cnblogs.com/jacklu/p/8379726.html

    用户7043923
  • 爬虫爬取英文文档存为PDF,在读取PDF自动翻译文档

    这几天在爬了Python的官方文档,但是它里面全是英文,只有数字,没有汉字,原谅我这个英语渣渣搞不懂,只能靠翻译了,如果是复制到百度翻译的话太慢...

    andrew_a
  • 国内2大Git代码托管网站

    可以说GitHub的出现完全颠覆了以往大家对代码托管网站的认识。GitHub不但是一个代码托管网站,更是一个程序员的SNS社区。GitHub真正迷人的是它的创新...

    张善友

扫码关注云+社区

领取腾讯云代金券