Python?遞歸式實現二叉樹前序,中序,后序遍歷

更新時間：2022年03月07日 16:39:58 作者：步木木

這篇文章主要介紹了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

# 用列表遞歸創(chuàng)建二叉樹
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 遞歸式實現二叉樹前序,中序,后序遍歷的文章就介紹到這了,更多相關二叉樹前序,中序,后序遍歷內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: