Python 递归式实现二叉树前序,中序,后序遍历

目录 1.前序遍历 2.中序遍历 3.后序遍历 4.测试 5.结果 6.补充 6.1N叉树前序遍历

记忆点：

前序：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

到此这篇关于Python 递归式实现二叉树前序,中序,后序遍历的文章就介绍到这了,更多相关二叉树前序,中序,后序遍历内容请搜索以前的文章或继续浏览下面的相关文章希望大家以后多多支持！

查看更多关于Python 递归式实现二叉树前序,中序,后序遍历的详细内容...

声明：本文来自网络，不代表【好得很程序员自学网】立场，转载请注明出处：http://www.haodehen.cn/did99586