当前位置:网站首页>[dai6] mirror image of JZ27 binary tree
[dai6] mirror image of JZ27 binary tree
2022-07-07 10:29:00 【strawberry47】
subject :
Operate a given binary tree , Transform it into a mirror image of the source binary tree .
Ideas
What returns is a tree , That has to be established TreeNode Well , Thought of two methods :
① Using the queue , Save from right to left node, The order read out in this way is mirrored ; But the answer requires outputting a tree , I don't know how to convert it into a tree
② Using recursion , When children are leaf nodes , Exchange the positions of the left and right nodes ; But I still can't write ,o(╥﹏╥)o
Secretly read the answer , Use the stack to store nodes , Exchange left and right nodes every time you take them out , So I wrote the code according to this idea :
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
#
# The class name in the code 、 Method name 、 The parameter name has been specified , Do not modify , Return the value specified by the method directly
#
#
# @param pRoot TreeNode class
# @return TreeNode class
#
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
answer :
Look at recursion :
The problem solving steps :
1、 Special judgement : If pRoot It's empty , Returns an empty
2、 Exchange left and right subtrees
3、 hold pRoot Put the left subtree of Mirror Mirror in
4、 hold pRoot The right subtree of Mirror Mirror in
5、 Return root node root
class Solution:
def Mirror(self , pRoot ):
# write code here
if not pRoot:
return pRoot
# Left and right subtrees exchange
pRoot.left, pRoot.right = pRoot.right, pRoot.left
# Recursive left and right subtrees
self.Mirror(pRoot.left)
self.Mirror(pRoot.right)
return pRoot
I searched the Internet for a recursive solution :
To solve the problem of recursion is usually a three-step process , Namely :
First step , Define function function -> Flip the tree
The second step , Looking for recursive termination conditions -> It is already a leaf node or It's already empty
The second step , The equivalent relation of recursive function -> Flip node The left and right subtrees of
边栏推荐
- 柏拉图和他的三个弟子的故事:如何寻找幸福?如何寻找理想伴侣?
- The mobile terminal automatically adjusts the page content and font size by setting rem
- Differences between MCU and MPU
- MySQL insert data create trigger fill UUID field value
- How embedded engineers improve work efficiency
- STM32 ADC和DMA
- Guid主键
- 嵌入式工程师如何提高工作效率
- Kotlin实现微信界面切换(Fragment练习)
- @Transcation的配置,使用,原理注意事项:
猜你喜欢
JMeter about setting thread group and time
成为优秀的TS体操高手 之 TS 类型体操前置知识储备
MySQL insert data create trigger fill UUID field value
浅谈日志中的返回格式封装格式处理,异常处理
IIC基本知识
Trajectory planning for multi-robot systems: Methods and applications 综述阅读笔记
openinstall与虎扑达成合作,挖掘体育文化产业数据价值
High number_ Chapter 1 space analytic geometry and vector algebra_ Quantity product of vectors
php \n 换行无法输出
Appx代碼簽名指南
随机推荐
The Hal library is configured with a general timer Tim to trigger ADC sampling, and then DMA is moved to the memory space.
[higherhrnet] higherhrnet detailed heat map regression code of higherhrnet
Talking about the return format in the log, encapsulation format handling, exception handling
IO model review
The method of word automatically generating directory
Kotlin实现微信界面切换(Fragment练习)
Slurm资源管理与作业调度系统安装配置
每周推荐短视频:L2级有哪些我们日常中经常会用到的功能?
table宽度比tbody宽度大4px
MySQL insert data create trigger fill UUID field value
The mobile terminal automatically adjusts the page content and font size by setting rem
求最大公约数与最小公倍数(C语言)
Inno setup packaging and signing Guide
Chris LATTNER, the father of llvm: why should we rebuild AI infrastructure software
反射效率为什么低?
P1031 [NOIP2002 提高组] 均分纸牌
【HigherHRNet】 HigherHRNet 详解之 HigherHRNet的热图回归代码
Remote meter reading, switching on and off operation command
STM32 ADC和DMA
【acwing】789. Range of numbers (binary basis)