首页 > 编程语言 >LeetCode Top100:二叉树的中序遍历(Python)

LeetCode Top100:二叉树的中序遍历(Python)

时间:2023-04-17 20:25:08浏览次数:43  
标签:遍历 Python 中序 right 二叉树 root self result

 

给定一个二叉树的根节点 root ,返回 它的 中序 遍历 。

 

示例 1:

输入:root = [1,null,2,3]
输出:[1,3,2]

示例 2:

输入:root = []
输出:[]

示例 3:

输入:root = [1]
输出:[1]

 

提示:

  • 树中节点数目在范围 [0, 100] 内
  • -100 <= Node.val <= 100

 

以下是一个Python程序,实现给定二叉树的中序遍历:

方案1: 

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        result = []
        self.inorder(root, result)
        return result
        
    def inorder(self, root, result):
        if root is None:
            return
        self.inorder(root.left, result)
        result.append(root.val)
        self.inorder(root.right, result)

首先定义了一个 TreeNode 类表示二叉树的节点。然后定义了一个 Solution 类,其中有一个 inorderTraversal 方法用于计算二叉树的中序遍历。在这个方法中,我们创建一个空列表 result,然后调用 inorder 方法进行实际的遍历。

在 inorder 方法中,我们首先检查根节点是否为 None,如果是,则直接返回。否则,我们递归地遍历左子树,将根节点的值添加到结果列表中,然后递归地遍历右子树。最终返回结果列表 result。

  

方案2: 

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        result = []
        stack = []
        while root or stack:
            while root:
                stack.append(root)
                root = root.left
            root = stack.pop()
            result.append(root.val)
            root = root.right
        return result

首先定义了一个 TreeNode 类表示二叉树的节点。然后定义了一个 Solution 类,其中有一个 inorderTraversal 方法用于计算二叉树的中序遍历。在这个方法中,我们创建一个空列表 result 用于存储遍历结果,创建一个空栈 stack,用于辅助遍历操作。

使用while循环和栈来实现遍历,当root不为None或者栈不为空时,进入循环。首先将当前节点及其所有左子节点都压入栈中,然后从栈中弹出栈顶元素,将其值添加到结果列表 result 中。接下来,将当前节点的右子节点作为下一轮循环的起点,即将 root 赋值为 root.right,继续进行遍历操作。

最终,返回结果列表 result,即为二叉树的中序遍历结果。

  

 

标签:遍历,Python,中序,right,二叉树,root,self,result
From: https://www.cnblogs.com/huadongw/p/17327356.html

相关文章

  • python爬虫scrapy框架的使用
    总结scrapystartprojectnamescrapygenspiderbaiduhttp://www.baidu.comscrapycrawlbaiduscrapy项目创建scrapystartprojectscrapy_baidu_091创建爬虫文件在spider中创建爬虫文件#scrapygenspider名称域名(不写http)scrapygenspiderbaiduhttp://www.b......
  • 基于Python程序模拟核酸检测寻找最优化方案
    本文中的数学建模问题来源于NKU的数学建模第二次实战演练,由于本次是我来进行程序的编写,故将代码与笔记记录在这里。问题提要现有800万市民报名参与核酸检测,如果对每人逐一进行检测,所需时间和检测能力都超过现实情况,所以拟采用混样检测(grouptesting)方式进行。先考虑混样规模为......
  • 二叉树中和为某一值的路径
    描述输入一颗二叉树的根节点root和一个整数expectNumber,找出二叉树中结点值的和为expectNumber的所有路径。1.该题路径定义为从树的根结点开始往下一直到叶子结点所经过的结点2.叶子节点是指没有子节点的节点3.路径只能从父节点到子节点,不能从子节点到父节点4.总节点数目为n如二叉......
  • Python替换文件内容
    文件部分内容如下:<mappingcell="A1">request.aaPriceChangeDesc</mapping><mappingcell="B1">request.aaStartDate</mapping><mappingcell="C1">request.aaSumCode</mapping><mappingcell=......
  • 自动化脚本:一键安装python自定义版本
     1:环境:centos7python2.72:脚本内容:#!/usr/bin/envpythonimportosimportsysimportrequestsimporttarfileimportshutilimportsubprocess#Installnecessarypackagestry:subprocess.check_call(["yum","install","-y&qu......
  • [oeasy]python0132_变量含义_meaning_声明_declaration_赋值_assignment
    变量定义回忆上次内容上次回顾了一下历史python是如何从无到有的看到Guido长期的坚持和努力 编程语言的基础都是变量声明python是如何声明变量的呢? 变量想要定义变量首先明确什么是变量变量就是数值能变的量英文名称varia......
  • [oeasy]python0132_变量含义_meaning_声明_declaration_赋值_assignment
    变量定义回忆上次内容上次回顾了一下历史python是如何从无到有的看到Guido长期的坚持和努力编程语言的基础都是变量声明python是如何声明变量的呢?变量想要定义变量首先明确什么是变量变量就是数值能变的量英文名称variable计算机在内存中分配出空间用来存储这些能变的量那......
  • random模块&string模块谈python中随机数
    一、概述随机数在程序设计中的属于比较基础的内容,主要用于验证场景(如验证码,生成账号对应的密码等),今天结合random模块和string模块来谈谈python中随机数那些事儿。二、随机数实现相关模块2.1random模块random.random()返回一个随机浮点数。>>>importrandom>>>print(ran......
  • PYTHON学习路径计划图整理
    PYTHON学习路径计划图Python工作环境及基础语法知识了解对于Python基础语法学习部分,学习周期大概为4周,需要的相关资源在网络上都能找到免费的资源,而且质量都不错。相关中文资源如下:1.python工作集成环境包Python(x,y): 下载地址Pycharm: 下载地址2.python数据分析相关库(Pa......
  • 功能不够用?使用C++编写通达信插件及接入Python(二)
    参考:https://zhuanlan.zhihu.com/p/613157262一、准备工作(参考上一篇)安装VS2019 安装pycharm下载 http://help.tdx.com.cn/book.asp《通达信DLL函数编程规范.rar》二、下载python3.x的32位版本,http://www.python.org,随便找个32位版就行了。我准备下载Windowsembeddabl......