当前位置:网站首页>[牛客网刷题 Day6] JZ27 二叉树的镜像
[牛客网刷题 Day6] JZ27 二叉树的镜像
2022-07-07 08:14:00 【strawberry47】
题目:
操作给定的二叉树,将其变换为源二叉树的镜像。
思路
返回的是一棵树,那得建立TreeNode吧,想到了两种方法:
① 使用队列,从右往左存node,这样读出来的顺序就是镜像的;可是答案要求输出一颗树,我不知道怎么转换成树
② 使用递归,当孩子为叶节点时,交换左右节点的位置;可是还是写不来,o(╥﹏╥)o
偷偷看了答案,用堆栈存储节点,每次取出来就交换左右节点,于是照着这个思路写了一下代码:
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
#
# 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
#
#
# @param pRoot TreeNode类
# @return TreeNode类
#
class Solution:
def Mirror(self , pRoot: TreeNode) -> TreeNode:
# write code here
if pRoot is None:
return None
q = []
q.append(pRoot)
while len(q):
for i in range(len(q)):
node = q.pop()
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
# swap
tmp = node.left
node.left = node.right
node.right = tmp
return pRoot
答案:
看了看递归:
解题步骤:
1、特判:如果pRoot为空,返回空
2、交换左右子树
3、把pRoot的左子树放到Mirror中镜像一下
4、把pRoot的右子树放到Mirror中镜像一下
5、返回根节点root
class Solution:
def Mirror(self , pRoot ):
# write code here
if not pRoot:
return pRoot
# 左右子树交换
pRoot.left, pRoot.right = pRoot.right, pRoot.left
# 递归左右子树
self.Mirror(pRoot.left)
self.Mirror(pRoot.right)
return pRoot
网上搜了一下递归的解法:
解决递归问题一般就三步曲,分别是:
第一步,定义函数功能 -> 翻转树
第二步,寻找递归终止条件 -> 已经是叶节点了or已经为空了
第二步,递推函数的等价关系式 -> 翻转node的左子树和右子树
边栏推荐
- 基于HPC场景的集群任务调度系统LSF/SGE/Slurm/PBS
- HAL库配置通用定时器TIM触发ADC采样,然后DMA搬运到内存空间。
- ArcGIS operation: batch modify attribute table
- Programming features of ISP, IAP, ICP, JTAG and SWD
- Apprentissage avancé des fonctions en es6
- 每周推荐短视频:L2级有哪些我们日常中经常会用到的功能?
- The variables or functions declared in the header file cannot be recognized after importing other people's projects and adding the header file
- MCU与MPU的区别
- 移动端通过设置rem使页面内容及字体大小自动调整
- Weekly recommended short videos: what are the functions of L2 that we often use in daily life?
猜你喜欢
【acwing】789. Range of numbers (binary basis)
Experience sharing of software designers preparing for exams
Appx代碼簽名指南
How to cancel automatic saving of changes in sqlyog database
Chris LATTNER, the father of llvm: why should we rebuild AI infrastructure software
Appx code signing Guide
字符串格式化
STM32基础知识—内存映射
ORM -- query type, association query
基于HPC场景的集群任务调度系统LSF/SGE/Slurm/PBS
随机推荐
Experience sharing of software designers preparing for exams
XML configuration file parsing and modeling
Postman tutorial - scripting
IO模型复习
Serial communication relay Modbus communication host computer debugging software tool project development case
嵌入式背景知识-芯片
Postman interface test I
Kotlin实现微信界面切换(Fragment练习)
Fiddler simulates the interface test
【HigherHRNet】 HigherHRNet 详解之 HigherHRNet的热图回归代码
VS Code指定扩展安装位置
How to cancel automatic saving of changes in sqlyog database
电表远程抄表拉合闸操作命令指令
Postman interface test III
@Transcation的配置,使用,原理注意事项:
HAL库配置通用定时器TIM触发ADC采样,然后DMA搬运到内存空间。
ES6中的函數進階學習
对存储过程进行加密和解密(SQL 2008/SQL 2012)
Easyexcel read write simple to use
2022.7.3DAY595