今天小编给大家分享一下怎么用Python递归式实现二叉树前序,中序,后序遍历的相关知识点，内容详细，逻辑清晰，相信大部分人都还太了解这方面的知识，所以分享这篇文章给大家参考一下，希望大家阅读完这篇文章后有所收获，下面我们一起来了解一下吧。
记忆点：
举例：
一颗二叉树如下图所示：
则它的前序、中序、后序遍历流程如下图所示：
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
以上就是“怎么用Python递归式实现二叉树前序,中序,后序遍历”这篇文章的所有内容，感谢各位的阅读！相信大家阅读完这篇文章都有很大的收获，小编每天都会为大家更新不同的知识，如果还想学习更多的知识，请关注天达云行业资讯频道。