怎么用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# 用列表递归创建二叉树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 resif __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 resN叉树后序遍历"""# 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频道。