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

灰太狼 2022-10-07 03:53 188阅读 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 条评论，188人围观）

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

相关阅读

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

什么树树是 n（n>=0）个有限集。n=0是空树，在n>1的非空树中有且仅有一个根节点作为树根，其他结构分散在根节点下形成一个个子树。各个子树互不相交。在实际的编码环节中

ゝ一纸荒年。/ 2024年03月30日 10:50/ 0 赞/ 80 阅读

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

【数据结构与算法之面试题】二叉树类面试题文章目录【数据结构与算法之面试题】二叉树类面试题 1 完全二叉树的判

港控/mmm°/ 2024年03月25日 23:01/ 0 赞/ 80 阅读

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXh

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