【数据结构与算法面试题】二叉树镜像

灰太狼 2022-10-07 03:53 167阅读 0赞

> 题目来源“[数据结构与算法面试题80道][80]”。

![这里写图片描述][53c8b426ecc6cd42794b0ebb2e3eacc3.png]

问题分析：实质上仍然是二叉树的遍历，上述已经介绍过二叉树的不同的遍历方法，当遍历到每一个节点的时候，交换其左右子树，依次下去，直到叶子节点。

方法：

1、递归的方法：

void tree_swap(BSTreeNode *root){
        BSTreeNode *p_tmp = root->m_pLeft;
        root->m_pLeft = root->m_pRight;
        root->m_pRight = p_tmp;
    }
    
    void tree_mirror(BSTreeNode *root){
        if (NULL == root ||
            (NULL == root->m_pLeft && NULL == root->m_pRight)){
            return;
        }
    
        tree_swap(root);
        tree_swap(root->m_pLeft);
        tree_swap(root->m_pRight);
    }

2、循环的方法

void tree_mirror_loop(BSTreeNode *root){
        if (NULL == root ||
            (NULL == root->m_pLeft && NULL == root->m_pRight)){
            return;
        }
    
        BSTreeNode *p = root;
        queue<BSTreeNode *> q_tree;
        q_tree.push(p);
        while (! q_tree.empty()){
            BSTreeNode *q = q_tree.front();
            q_tree.pop();
            if (NULL != q->m_pLeft || NULL != q->m_pRight){
                tree_swap(q);
            }
            if (NULL != q->m_pLeft) q_tree.push(q->m_pLeft);
            if (NULL != q->m_pRight) q_tree.push(q->m_pRight);
        }
    }

[80]: https://yq.aliyun.com/articles/40478?utm_content=m_15768
[53c8b426ecc6cd42794b0ebb2e3eacc3.png]: /images/20221005/450f12b1298e4328ae8b37f6dda8a117.png

发表评论取消回复

表情：

评论列表（有 0 条评论，167人围观）

还没有评论，来说两句吧...

相关阅读

相关数据结构与算法（二） 02-对称二叉树和二叉树镜像

文章目录对称二叉树、二叉树镜像、二叉搜索树、二叉树深度 1 对称二叉树题目思路代

傷城~/ 2023年01月03日 04:24/ 0 赞/ 147 阅读

相关【数据结构与算法】二叉树

树 1.树、二叉树 2.二叉查找树 3.平衡二叉树、红黑树 4.递归树一、树 1.树的常用概念根节点、叶子节点、父节点、子节点、兄弟节点，还有节

逃离我推掉我的手/ 2022年11月29日 05:49/ 0 赞/ 216 阅读

相关【数据结构与算法面试题】二叉树路径查找

> 题目来源“[数据结构与算法面试题80道][80]”。 > ![这里写图片描述][850ae70e215a135386d1a92127e69abf.png] 问题分析：

迈不过友情╰/ 2022年10月07日 03:53/ 0 赞/ 166 阅读

相关【数据结构与算法面试题】二叉树镜像

> 题目来源“[数据结构与算法面试题80道][80]”。 ![这里写图片描述][53c8b426ecc6cd42794b0ebb2e3eacc3.png] 问题分析：实质上

灰太狼/ 2022年10月07日 03:53/ 0 赞/ 168 阅读

相关【数据结构】二叉树面试题总结

为了对二叉树的知识进行巩固，今天我们来解析5道二叉树的经典面试题。这五道面试题如下： 1. 求二叉树中最远两个结点的距离； 2. 判断一棵树是否是完全二叉树； 3.

朴灿烈づ我的快乐病毒、/ 2022年07月14日 07:16/ 0 赞/ 204 阅读

相关数据结构 - 二叉树 - 面试中常见的二叉树算法题

数据结构 - 二叉树 - 面试中常见的二叉树算法题数据结构是面试中必定考查的知识点，面试者需要掌握几种经典的数据结构：线性表（数组、链表）、栈与队列、树（二叉树、二叉查

蔚落/ 2022年06月01日 02:41/ 0 赞/ 227 阅读

相关【数据结构与算法】树（二）：二叉树

二叉树的特点每个结点最多有两颗子树，所以二叉树的度最大就是2. 左子树和右子树是由顺序的，不能够颠倒，即使树中只有一颗子树，也是要区分它是左子树还是右子树的

骑猪看日落/ 2022年05月21日 06:58/ 0 赞/ 287 阅读

相关数据结构与算法二叉树

数据结构与算法二叉树一、简述记--简单的有序链式二叉树添加、删除、遍历操作例子，有序：左孩子<父节点<右孩子。二、例子输入正数

柔情只为你懂/ 2022年05月17日 03:47/ 0 赞/ 264 阅读

相关二叉查找树-二叉树-数据结构与算法

C++ 语言: 二叉查找树二叉查找树(Binary Search Tree)，又被称为二叉搜索树。它是特殊的二叉树：对于二叉树，假设x为二叉树中的任意一个结点，x节

以你之姓@/ 2022年02月18日 20:51/ 0 赞/ 342 阅读

相关二叉树（数据结构与算法）

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXh

￡神魔★判官ぃ/ 2021年12月24日 00:34/ 0 赞/ 329 阅读