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

今天小編給大家分享一下怎么用Python遞歸式實現二叉樹前序,中序,后序遍歷的相關知識點，內容詳細，邏輯清晰，相信大部分人都還太了解這方面的知識，所以分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后有所收獲，下面我們一起來了解一下吧。

記憶點：

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

# 用列表遞歸創(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遞歸式實現二叉樹前序,中序,后序遍歷”這篇文章的所有內容，感謝各位的閱讀！相信大家閱讀完這篇文章都有很大的收獲，小編每天都會為大家更新不同的知識，如果還想學習更多的知識，請關注億速云行業(yè)資訊頻道。