当前位置:网站首页>二叉树 | 翻转二叉树 | leecode刷题笔记
二叉树 | 翻转二叉树 | leecode刷题笔记
2022-08-10 22:23:00 【Begonia_cat】
跟随carl代码随想录刷题
语言:python
226. 简单
翻转二叉树
题目:给你一棵二叉树的根节点 root ,翻转这棵二叉树,并返回其根节点。
输入:root = [4,2,7,1,3,6,9]
输出:[4,7,2,9,6,3,1]
题目分析
思路:交换每个节点的左右节点即可root.left, root.right = root.right, root.left
方法选择:
- 前序遍历
- 中序遍历【不能用,因为会把所有节点交换两次】
- 后序遍历
- 层序遍历
完整代码如下
方法1.1:前序遍历——递归法
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if root == None:
return None
# 交换节点
root.left, root.right = root.right, root.left # 中
self.invertTree(root.left) # 左
self.invertTree(root.right) # 右
return root
方法1.2:后序遍历——递归法
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if root == None:
return None
self.invertTree(root.left) # 左
self.invertTree(root.right) # 右
# 交换节点
root.left, root.right = root.right, root.left # 中
return root
方法2.1:前序遍历——迭代法
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root:
return None
st = []
st.append(root)
while st:
node = st.pop()
node.left, node.right = node.right, node.left # 中
if node.right:
st.append(node.right) # 左
if node.left:
st.append(node.left) # 右
return root
方法2.2:后序遍历——迭代法
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root:
return None
st = []
st.append(root)
while st:
node = st.pop()
if node.right:
st.append(node.right) # 左
if node.left:
st.append(node.left) # 右
node.left, node.right = node.right, node.left # 中
return root
方法3:层序遍历
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root:
return None
from collections import deque
que = deque([root])
while que:
size = len(que)
cur = que.popleft()
cur.left, cur.right = cur.right, cur.left
if cur.left:
que.append(cur.left)
if cur.right:
que.append(cur.right)
return root
边栏推荐
- ArcGIS应用基础知识
- QT笔记——用VS + qt 生成dll 和 调用生成的dll
- Glide监听Activity生命周期源码分析
- unusual understanding
- OneNote tutorial, how to organize notebooks in OneNote?
- Spark基础【RDD转换算子】
- DC-8靶场下载及渗透实战详细过程(DC靶场系列)
- STL-stack
- 解码2022中国网安强星丨正向建、反向查,华为构建数字化时代的网络安全防线
- August 10, 2022: Building Web Applications for Beginners with ASP.NET Core -- Creating Web UIs with ASP.NET Core
猜你喜欢
解码2022中国网安强星丨正向建、反向查,华为构建数字化时代的网络安全防线
12 Recurrent Neural Network RNN2 of Deep Learning
常用代码扩展点设计方式
Detailed installation steps and environment configuration of geemap
virtual address space
Translating scientific and technological papers, how to translate from Russian to Chinese
计算需要的MIPI lane数目
How many threads does LabVIEW allocate?
MySQL: MySQL Cluster - Principle and Configuration of Master-Slave Replication
实例049:lambda
随机推荐
谁是边缘计算服务的采购者?是这六个关键角色
TCP连接过程中如果拔掉网线会发生什么?
“数据引擎”开启前装规模量产新赛道,「智协慧同」崭露头角
文件IO-缓冲区
ASCII、Unicode和UTF-8
Why general company will say "go back messages such as" after the end of the interview, rather than just tell the interviewer the result?
合并k个已排序的链表
JS use regular expressions in g model and non g difference
水果沙拉酱
pytorch tear CNN
新一代网络安全防护体系的五个关键特征
亲测有效|处理风控数据特征缺失的一种方法
BM13判断一个链表是否为回文结构
DC-7靶场下载及渗透实战详细过程(DC靶场系列)
Lambda
元宇宙社交应用,靠什么吸引用户「为爱发电」?
字节跳动原来这么容易就能进去...
测试4年感觉和1、2年时没什么不同?这和应届生有什么区别?
Nodes in the linked list are flipped in groups of k
DC-9靶场下载及渗透实战详细过程(DC靶场系列)