每日一练(15):二叉树的镜像

简介: 请完成一个函数,输入一个二叉树,该函数输出它的镜像。

请完成一个函数,输入一个二叉树,该函数输出它的镜像。


例如输入:


    4

  /   \

 2      7

/   \   /  \

1   3   6   9


镜像输出:

     4

  /     \

 7       2

/   \   /   \

9    6   3   1


示例 1:


输入:root = [4,2,7,1,3,6,9]

输出:[4,7,2,9,6,3,1]


限制:

0 <= 节点个数 <= 1000


来源:力扣(LeetCode)


链接:https://leetcode-cn.com/probl...


方法一:递归


思路与算法


这是一道很经典的二叉树问题。显然,我们从根节点开始,递归地对树进行遍历,并从叶子节点先开始翻转得到镜像。如果当前遍历到的节点 root 的左右两棵子树都已经翻转得到镜像,那么我们只需要交换两棵子树的位置,即可得到以 root 为根节点的整棵子树的镜像。


//1
TreeNode* mirrorTree(TreeNode* root) {
    if (root == nullptr) {
        return nullptr;
    }
    TreeNode *left = mirrorTree(root->left);
    TreeNode *right = mirrorTree(root->right);
    root->left = right;
    root->right = left;
    return root;
}
//2
TreeNode* mirrorTree(TreeNode* root) {
    if (root == nullptr) {
        return nullptr;
    }
    swap(root->left, root->right);//交换左右节点
    mirrorTree(root->left);//对右节点递归
    mirrorTree(root->right);//对左节点递归
    return root;
}


方法二:迭代(栈/队列)


利用栈(或队列)遍历树的所有节点 node ,并交换每个 node 的左 / 右子节点。


算法流程:


  • 特例处理: 当 root 为空时,直接返回 null ;
  • 初始化: 栈(或队列),本文用栈,并加入根节点 root 。
  • 循环交换: 当栈 stack 为空时跳出;
  • 出栈: 记为 node ;
  • 添加子节点: 将 node 左和右子节点入栈;
  • 交换: 交换 node 的左 / 右子节点。


返回值: 返回根节点 root 。


复杂度分析:


  • 时间复杂度 O(N) : 其中 N 为二叉树的节点数量,建立二叉树镜像需要遍历树的所有节点,占用 O(N) 时间。
  • 空间复杂度 O(N) : 如下图所示,最差情况下,栈 stack 最多同时存储 ( N+1 )/ 2 个节点,占用 O(N) 额外空间。


// 迭代
// 栈
TreeNode* mirrorTree(TreeNode* root) {
    if (root == nullptr) {
        return nullptr;
    }
    stack<TreeNode*> sck;
    sck.push(root);
    while (!sck.empty()) {
        TreeNode* tmp = sck.top();
        sck.pop();
        if (!tmp) {
            continue;
        }
        swap(tmp->left,tmp->right);
        if(tmp->right != NULL) {
            sck.push(tmp->right);
        }
        if(tmp->left != NULL) {
            sck.push(tmp->left);
        }
    }
    return root;
}
// 队列
TreeNode* mirrorTree(TreeNode* root) {
    if (root == nullptr) {
        return nullptr;
    }
    queue<TreeNode*> que;
    que.push(root);
    while (!que.empty()) {
        TreeNode* tmp = que.front();
        que.pop();
        if(tmp == NULL) {
            continue;
        }
        swap(tmp->left,tmp->right);
        if(tmp->left) {
            que.push(tmp->left);
        }
        if(tmp->right) {
            que.push(tmp->right);
        }
    }
    return root;
}
目录
相关文章
|
存储 数据安全/隐私保护 网络架构
vue3用户权限管理(导航栏权限控制)2
上一节我们说到,通过后端的用户权限来进行路由的动态添加,实现权限控制,这一节我们通过递归导航栏组件,实现后台权限控制导航栏,接上一节所说我们在vuex中存储了一个路由数组["/","*"]进行权限控制,这一节还是要使用这个路由数组进行导航栏的控制,开始吧。
346 0
|
算法 安全 应用服务中间件
ECC+RSA双证书解决方案
ECC+RSA双算法SSL证书的配置方法
1641 0
|
9月前
|
弹性计算 Ubuntu Linux
阿里云服务器一键安装Docker社区版教程,基于系统运维管理OOS
阿里云服务器一键安装Docker社区版教程,基于系统运维管理OOS自动化部署。支持Ubuntu 22.04/20.04、CentOS 7.7-7.9及Alibaba Cloud Linux 3.2104 LTS。前提条件:ECS实例需运行中且有公网。步骤:选择Docker扩展并安装,验证成功通过命令`docker -v`查看版本号。
633 79
|
8月前
|
机器学习/深度学习 自然语言处理 监控
深入探索:深度学习在时间序列预测中的强大应用与实现
时间序列分析是数据科学和机器学习中一个重要的研究领域,广泛应用于金融市场、天气预报、能源管理、交通预测、健康监控等多个领域。时间序列数据具有顺序相关性,通常展示出时间上较强的依赖性,因此简单的传统回归模型往往不能捕捉其中复杂的动态特征。深度学习通过其非线性建模能力和层次结构的特征提取能力,能够有效地捕捉复杂的时间相关性和非线性动态变化模式,从而在时间序列分析中展现出极大的潜力。
|
11月前
|
数据采集 缓存 前端开发
服务器端渲染(SSR)
服务器端渲染(SSR)
|
11月前
|
数据采集 网络协议 算法
移动端弱网优化专题(十四):携程APP移动网络优化实践(弱网识别篇)
本文从方案设计、代码开发到技术落地,详尽的分享了携程在移动端弱网识别方面的实践经验,如果你也有类似需求,这篇文章会是一个不错的实操指南。
267 1
|
12月前
|
机器学习/深度学习
深度学习笔记(一): 神经网络之感知机详解
深度学习笔记(一):探索感知机模型及其在神经网络中的应用。
184 0
深度学习笔记(一): 神经网络之感知机详解
|
12月前
|
JavaScript 前端开发 算法
虚拟 DOM 是什么?
【10月更文挑战第18天】虚拟 DOM 是前端框架中的一项重要技术,它通过抽象和优化 DOM 操作,为前端应用带来了更好的性能、开发效率和可维护性。
465 1
|
分布式计算 资源调度 Hadoop
Hadoop 2.0 与 Hadoop 1.x 有何不同?
【8月更文挑战第12天】
272 4
|
监控 前端开发 API
错误码设计规范探索
本文介绍了错误码设计规范,包括模块化分层、错误码结构及定义、可扩展性与可维护性等方面。错误码用于标识程序中的特定错误,便于快速定位和解决。文中详细描述了全局通用错误码和业务错误码的设计方法,并提出了5-6位数字编码方案,确保错误码的唯一性和可读性。同时,强调了错误码与日志系统的集成及多语言支持的重要性,提供了多个参考文献供进一步学习。
1181 2