每日一练(15)(二叉树的镜像)
title: 每日一练(15):二叉树的镜像
categories:[剑指offer]
tags:[每日一练]
date: 2022/01/28
每日一练(15):二叉树的镜像
请完成一个函数,输入一个二叉树,该函数输出它的镜像。
【每日一练(15)(二叉树的镜像)】例如输入:
4
/\
27
/\/\
1369
镜像输出:
4
/\
72
/\/\
9631
示例 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 的左 / 右子节点。
复杂度分析:
- 时间复杂度 O(N) : 其中 N 为二叉树的节点数量,建立二叉树镜像需要遍历树的所有节点,占用 O(N) 时间。
- 空间复杂度 O(N) : 如下图所示,最差情况下,栈 stack 最多同时存储 ( N+1 )/ 2 个节点,占用 O(N) 额外空间。
// 迭代
// 栈
TreeNode* mirrorTree(TreeNode* root) {
if (root == nullptr) {
return nullptr;
}
stack 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 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;
}
推荐阅读
- 每日一话(49)——一位清华教授在朋友圈给大学生的9条建议
- java中如何实现重建二叉树
- 两感一练
- #2018.4.12#每日一问#+简宁+D03+我是怎样做读书笔记的
- 每日微习惯诞生|每日微习惯诞生 16/100
- 二叉树路径节点关键值和等于目标值(LeetCode--112&LeetCode--113)
- --木木--|--木木-- 第二课作业#翼丰会(每日一淘6+1实战裂变被动引流# 6+1模式)
- 03月30日|03月30日|Day92|每日复盘
- [白雪扇贝每日一句特训班]week5复盘——相信持续的力量
- 4.4每日一思之清明节