Python 递归式实现二叉树前序,中序,后序遍历
作者:步木木 时间:2022-09-22 17:38:32
记忆点:
前序:VLR
中序:LVR
后序:LRV
举例:
一颗二叉树如下图所示:
则它的前序、中序、后序遍历流程如下图所示:
1.前序遍历
class Solution:
def preorderTraversal(self, root: TreeNode):
def preorder(root: TreeNode):
if not root:
return
res.append(root.val)
preorder(root.left)
preorder(root.right)
res = []
preorder(root)
return res
2.中序遍历
class Solution:
def inorderTraversal(self, root: TreeNode):
def inorder(root: TreeNode):
if not root:
return
inorder(root.left)
res.append(root.val)
inorder(root.right)
res = []
inorder(root)
return res
3.后序遍历
class Solution:
def postorderTraversal(self, root: TreeNode):
def postorder(root: TreeNode):
if not root:
return
postorder(root.left)
res.append(root.val)
postorder(root.right)
res = []
postorder(root)
return res
4.测试
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# 用列表递归创建二叉树
def createTree(root,list_n,i):
if i <len(list_n):
if list_n[i] == 'null':
return None
else:
root = TreeNode(val = list_n[i])
root.left = createTree(root.left,list_n,2*i+1)
root.right = createTree(root.right,list_n,2*i+2)
return root
return root
class Solution:
def preorderTraversal(self, root: TreeNode): # 前序
def preorder(root: TreeNode):
if not root:
return
res.append(root.val)
preorder(root.left)
preorder(root.right)
res = []
preorder(root)
return res
def inorderTraversal(self, root: TreeNode): # 中序
def inorder(root: TreeNode):
if not root:
return
inorder(root.left)
res.append(root.val)
inorder(root.right)
res = []
inorder(root)
return res
def postorderTraversal(self, root: TreeNode): # 后序
def postorder(root: TreeNode):
if not root:
return
postorder(root.left)
postorder(root.right)
res.append(root.val)
res = []
postorder(root)
return res
if __name__ == "__main__":
root = TreeNode()
list_n = [1,2,3,4,5,6,7,8,'null',9,10]
root = createTree(root,list_n,0)
s = Solution()
res_pre = s.preorderTraversal(root)
res_in = s.inorderTraversal(root)
res_post = s.postorderTraversal(root)
print(res_pre)
print(res_in)
print(res_post)
5.结果
6.补充
6.1N叉树前序遍历
"""
# Definition for a Node.
class Node:
def __init__(self, val=None, children=None):
self.val = val
self.children = children
"""
class Solution:
def postorder(self, root: 'Node') -> List[int]:
def seq(root):
if not root:
return
res.append(root.val)
for child in root.children:
seq(child)
res = []
seq(root)
return res
N叉树后序遍历
"""
# Definition for a Node.
class Node:
def __init__(self, val=None, children=None):
self.val = val
self.children = children
"""
class Solution:
def postorder(self, root: 'Node') -> List[int]:
def seq(root):
if not root:
return
for child in root.children:
seq(child)
res.append(root.val)
res = []
seq(root)
return res
来源:https://blog.csdn.net/weixin_44241793/article/details/123280376
标签:Python,递归式,二叉树,前序,中序,后序,遍历
0
投稿
猜你喜欢
重新认识CSS的权重
2011-05-24 17:06:00
PHP中$GLOBALS['HTTP_RAW_POST_DATA']和$_POST的区别分析
2023-11-22 22:00:16
pytest解读fixtures之Teardown处理yield和addfinalizer方案
2023-06-18 22:13:01
理解和使用Oracle 8i分析工具LogMiner
2010-07-16 13:22:00
使用python语言,比较两个字符串是否相同的实例
2023-08-24 15:01:14
简单介绍各种浏览器中的本地存储方法
2012-04-26 16:37:34
SQL大讲堂:如何了解SQL的执行频率
2009-09-05 09:40:00
混乱的标记语言XHTML2/HTML5
2009-07-31 14:27:00
彻底弄懂CSS盒子模式之四(绝对定位和相对定位)
2007-05-11 16:51:00
asp如何将数字转化成条形图?
2009-12-03 20:19:00
正则表达式不匹配某个字符串
2010-03-02 22:08:00
SQL查询不重复记录/删除重复记录
2008-11-18 16:08:00
查找备注(text,ntext)类型字段为空的方法
2008-08-02 12:47:00
PHP基于phpqrcode类生成二维码的方法示例详解
2023-07-15 22:57:52
SQL Server数据体系和应用程序逻辑详解
2009-04-14 07:23:00
在Recordset对象中查询记录的方法
2008-11-20 16:51:00
教你如何将 Sublime 3 打造成 Python/Django IDE开发利器
2022-10-10 11:37:29
Python数据类型转换详解
2021-03-04 04:11:13
面向对象CSS FAQ[译]
2009-10-27 15:59:00
oracle应用程序实现打包 的方法
2009-03-02 10:32:00