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 递归式实现二叉树前序,中序,后序遍历的文章就介绍到这了,更多相关二叉树前序,中序,后序遍历内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • Python二叉树的遍历操作示例【前序遍历,中序遍历,后序遍历,层序遍历】

    本文实例讲述了Python二叉树的遍历操作.分享给大家供大家参考,具体如下: # coding:utf-8 """ @ encoding: utf-8 @ author: lixiang @ email: lixiang_cn@foxmail.com @ python_version: 2 @ time: 2018/4/11 0:09 @ more_info: 二叉树是有限个元素的集合,该集合或者为空.或者有一个称为根节点(root)的元素及两个互不相交的.分别被称为左子树和

  • Python实现二叉树前序、中序、后序及层次遍历示例代码

    前言 树是数据结构中非常重要的一种,主要的用途是用来提高查找效率,对于要重复查找的情况效果更佳,如二叉排序树.FP-树.另外可以用来提高编码效率,如哈弗曼树. 用 Python 实现树的构造和几种遍历算法.实现功能如下: 树的构造 递归实现先序遍历.中序遍历.后序遍历 堆栈实现先序遍历.中序遍历.后序遍历 队列实现层次遍历 # -*- coding=utf-8 -*- class Node(object): """节点类""" def __ini

  • 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 ro

  • C++ 数据结构二叉树(前序/中序/后序递归、非递归遍历)

    C++ 数据结构二叉树(前序/中序/后序递归.非递归遍历) 二叉树的性质: 二叉树是一棵特殊的树,二叉树每个节点最多有两个孩子结点,分别称为左孩子和右孩子. 例: 实例代码: #include <iostream> #include <Windows.h> #include <stack> using namespace std; template <class T> struct BinaryTreeNode { int _data; BinaryTree

  • C++二叉树的前序中序后序非递归实现方法详细讲解

    目录 二叉树的前序遍历 二叉树的中序遍历 二叉树的后序遍历 总结 二叉树的前序遍历 前序遍历的顺序是根.左.右.任何一颗树都可以认为分为左路节点,左路节点的右子树.先访问左路节点,再来访问左路节点的右子树.把访问左路节点的右子树看成一个子问题,就可以完整递归访问了. 先定义栈st存放节点.v存放值,TreeNode* cur,cur初始化为root. 当cur不为空或者栈不为空的时候(一开始栈是空的,cur不为空),循环继续:先把左路节点存放进栈中,同时把值存入v中,一直循环,直到此时的左路节点

  • C语言二叉树常见操作详解【前序,中序,后序,层次遍历及非递归查找,统计个数,比较,求深度】

    本文实例讲述了C语言二叉树常见操作.分享给大家供大家参考,具体如下: 一.基本概念 每个结点最多有两棵子树,左子树和右子树,次序不可以颠倒. 性质: 1.非空二叉树的第n层上至多有2^(n-1)个元素. 2.深度为h的二叉树至多有2^h-1个结点. 满二叉树:所有终端都在同一层次,且非终端结点的度数为2. 在满二叉树中若其深度为h,则其所包含的结点数必为2^h-1. 完全二叉树:除了最大的层次即成为一颗满二叉树且层次最大那层所有的结点均向左靠齐,即集中在左面的位置上,不能有空位置. 对于完全二叉

  • 探讨:C++实现链式二叉树(用非递归方式先序,中序,后序遍历二叉树)

    如有不足之处,还望指正! 复制代码 代码如下: // BinaryTree.cpp : 定义控制台应用程序的入口点.//C++实现链式二叉树,采用非递归的方式先序,中序,后序遍历二叉树#include "stdafx.h"#include<iostream>#include<string>#include <stack>using namespace std;template<class T>struct BiNode{ T data; 

  • PHP实现二叉树深度优先遍历(前序、中序、后序)和广度优先遍历(层次)实例详解

    本文实例讲述了PHP实现二叉树深度优先遍历(前序.中序.后序)和广度优先遍历(层次).分享给大家供大家参考,具体如下: 前言: 深度优先遍历:对每一个可能的分支路径深入到不能再深入为止,而且每个结点只能访问一次.要特别注意的是,二叉树的深度优先遍历比较特殊,可以细分为先序遍历.中序遍历.后序遍历.具体说明如下: 前序遍历:根节点->左子树->右子树 中序遍历:左子树->根节点->右子树 后序遍历:左子树->右子树->根节点 广度优先遍历:又叫层次遍历,从上往下对每一层依

  • 二叉树递归迭代及morris层序前中后序遍历详解

    目录 分析二叉树的前序,中序,后序的遍历步骤 1.层序遍历 方法一:广度优先搜索 方法二:递归 2.前序遍历 3.中序遍历 4.后序遍历 递归解法 前序遍历--递归 迭代解法 前序遍历--迭代 核心思想: 三种迭代解法的总结: Morris遍历 morris--前序遍历 morris--中序遍历 morris--后序遍历: 分析二叉树的前序,中序,后序的遍历步骤 1.层序遍历 方法一:广度优先搜索   (以下解释来自leetcode官方题解) 我们可以用广度优先搜索解决这个问题. 我们可以想到最

  • Java数据结构最清晰图解二叉树前 中 后序遍历

    目录 一,前言 二,树 ①概念 ②树的基础概念 三,二叉树 ①概念 ②两种特殊的二叉树 ③二叉树的性质 四,二叉树遍历 ①二叉树的遍历 ②前序遍历 ③中序遍历 ④后序遍历 五,完整代码 一,前言 二叉树是数据结构中重要的一部分,它的前中后序遍历始终贯穿我们学习二叉树的过程,所以掌握二叉树三种遍历是十分重要的.本篇主要是图解+代码Debug分析,概念的部分讲非常少,重中之重是图解和代码Debug分析,我可以保证你看完此篇博客对于二叉树的前中后序遍历有一个新的认识!!废话不多说,让我们学起来吧!!

随机推荐