欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

二叉树的镜像

程序员文章站 2022-06-01 08:46:21
...

剑指Offer_19 二叉树的镜像


2018/5/21 星期一

题目: 请完成一个函数,输入二叉树,该函数输出它的镜像。二叉树的结点定义:

class BinaryTreeNode {
    int data;
    BinaryTreeNode leftNode;
    BinaryTreeNode rightNode;
}

例如:下面图片的
二叉树的镜像)

分析:上图中,由图左到图右可以经过如下的变换:

  1. 首先交换根结点8的左、右子树(6、10)结点。
  2. 然后再分别交换(6、10)的左右子树;迭代
  3. 迭代条件就是到达了叶子结点。

具体的交换过程如下图:

二叉树的镜像

总结上面的过程就是:我们先序遍历每个结点,如果遍历到有子结点,就交换它的两个子结点。当交换完所有的非叶子结点的左右子结点之后,就可以得到树的镜像

上面的参考代码:

BinaryTreeNode MirrorRecursively(BinaryTreeNode pNode) {
    if (pNode != null) {
        BinaryTreeNode node = pNode.leftNode;
        pNode.leftNode = pNode.rightNode;
        pNode.rightNode = node;
        if (pNode.leftNode != null) {
            MirrorRecursively(pNode.leftNode);
        }
        if (pNode.rightNode != null) {
            MirrorRecursively(pNode.rightNode);
        }
    }
    return pNode;
}

测试用例

  1. 功能测试:普通的二叉树,只有右子树,只有左子树,这有一个结点;
  2. 特殊输入测试:二叉树的根结点为null。

本题扩展:

上面是考虑使用递归实现,如何要求用循环,该如何实现?