Leetcode中二叉树问题汇总(一)

标签: 二叉树

最近陆陆续续在刷树结构这类的问题,非线性结构的问题一直是软肋,尤其是这类问题大量使用递归,对于我这种混了好几年的小白来说不容易理解,因此针对Leetcode中树这一类问题进行了下总结,温故而知新嘛(之前学的都还给老师了…),本文主要讲基本操作的编码实现,同时也希望各位大神批评指正。

二叉树的基本概念具体可以参考:度娘带你走进二叉树

二叉树结构

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

leetcode中给出了节点类的定义,方便我们在编码的过程中确认变量名的使用问题,但是并没有给出创建的过程,在leetcode环境中,大多是传入一个列表,通过列表的层次顺序进行自上到下的构建。因此在本地IDE中进行调试的过程中,需要先编写构造规则再编写相关逻辑。

二叉树的构建

二叉树的递归层次构造

    def createBiTree(self, root, lis, index):
        if index < len(lis):
            if lis[index] is None:
                return None
            root = TreeNode(lis[index])
            #列表中索引为index的值,当它作为父节点时,子节点位于原列表索引为2*index+1
            #和2*index+2处
            root.left = root.createBiTree(root.left, lis, 2*index + 1)
            root.right = root.createBiTree(root.right, lis, 2*index + 2)
            return root
        return root

传入的参数是一个root节点(空值,初始化树),给定列表,和索引值(从列表的第一个元素开始,初始为0)。

二叉树的非递归层次构造

    def createBiTree(self,lis):
        if len(lis) == 0:
            return None
        queue = []
        #根节点入队列
        root = TreeNode(lis.pop(0))
        queue.append(root)
        while len(lis) > 0:
            #temp为下一层的节点
            temp = []
            for i in range(0,len(queue)):
                #本层中的节点依次出队
                node = queue[i]
                #判断本层节点左右孩子的情况
                if len(lis) != 0:
                    #从原始列表中弹出第一个元素(从左到右)
                    left = lis.pop(0)
                    if left is not None:
                        node.left = TreeNode(left)
                        #不为空时,将构造的节点存入temp中
                        temp.append(node.left)
                if len(lis) != 0:
                    right = lis.pop(0)
                    if right is not None:
                        node.right = TreeNode(right)
                        temp.append(node.right)
            #遍历完本层节点后,将下一层节点作为下一次遍历的对象
            queue = temp
        return root

非递归构造的传入参数为所需构造的列表,借用队列这一逻辑结构辅助完成(python中创建栈和队列的方式如此方便,有啥理由不爱上她!)
上述的构造只针对在进行leetcode相关二叉树问题线下调试的环节,下面说一下前序中序后序和层次遍历这些基础操作。

二叉树的遍历

二叉树的遍历在百度google铺天盖地的都是,这类基本操作难度不大,但是是二叉树的基础。

前序递归遍历二叉树

    def preorderTraversal(self,root):
        #由于返回值是以列表的形式,因此利用函数嵌套的方式
        result = []
        def impl(root):
            if root is None:
                return None
            result.append(root.value)
            root.left = impl(root.left)
            root.right = impl(root.right)
        root = impl(root)
        return result

前序遍历的遍历顺序是根节点—>左子—>右子,如图是一棵二叉树(引用自百度百科):
这里写图片描述

在本地构建时先传入列表[‘F’,’C’,’E’,’A’,’D’,’H’,’G’,None,None,’B’,None,None,None,’M’,None],None表示节点为空,进行树的构建,之后从根节点开始,依次遍历每个被访问节点的左右子,直至子节点为空。前序遍历的顺序是[‘F’, ‘C’, ‘A’, ‘D’, ‘B’, ‘E’, ‘H’, ‘G’, ‘M’]。

前序非递归遍历二叉树

    def preorderTraversal(self,root):
        result = []
        stack = []
        if root is None:
            return result
        stack.append(root)
        while len(stack) > 0:
            node = stack.pop()
            if node:
                result.append(node.value)
                stack.append(node.right)
                stack.append(node.left)
        return result

前序遍历的非递归方法用栈结构实现,基本思想是访问根节点后,先将其右子压栈(之所以这样做是在出栈时保证左子先出),若左子不为空,则沿左子依此访问(对于一个父节点来说,保证其左子树的所有节点都已经遍历过,再开始将右子树的根节点出栈)。代码的问题是不管是否为空都有压栈的操作,会造成频繁进栈出栈的问题,因此可以先判断是否为空再考虑是否压栈。

中序递归遍历二叉树

    def inorderTraversal(self, root):
        result = []
        def impl(root):
            if root is None:
                return None
            root.left = impl(root.left)
            result.append(root.value)
            root.right = impl(root.right)
        root = impl(root)
        return result

中序遍历的遍历顺序是左子—>根节点—>右子,实现方法和前序遍历相似,只是先递归遍历左子直至叶子节点。就前面的图来说,其遍历顺序为[‘A’, ‘C’, ‘B’, ‘D’, ‘F’, ‘H’, ‘E’, ‘M’, ‘G’]。

中序非递归遍历二叉树

    def inorderTraversal(self,root):
        result = []
        stack = []
        if root is None:
            return result
        node = root
        while node or len(stack) > 0:
            if node:
                stack.append(node)
                node = node.left
            else:
                node = stack.pop()
                result.append(node.value)
                node = node.right
        return result

由于中序遍历时第一个访问的节点应该是根节点左子树的最左节点,因此中序非递归遍历方法的基本思想是先沿着每个节点的左子进行搜索,同时进行压栈操作,直到当前节点为根节点左子树的最左节点(此时其左子树为空),将其存入结果列表中,然后再访问其右子。

后序递归遍历二叉树

    def postorderTraversal(self, root):
        result = []
        def impl(root):
            if root is None:
                return None
            root.left = impl(root.left)
            root.right = impl(root.right)
            result.append(root.value)
        root = impl(root)
        return result

后序遍历的遍历顺序是左子—>右子—>根节点,由此可见,二叉树的前中后遍历是从父节点的角度出发,先访问父节点则为前序,第二顺位访问父节点则为中序,最后被访问则为后序。对于前面的图来说,其后序遍历的顺序是[‘A’, ‘B’, ‘D’, ‘C’, ‘H’, ‘M’, ‘G’, ‘E’, ‘F’]。

后序非递归遍历二叉树

    def postorderTraversal(self, root):
        stack = []
        result = []
        if root is None:
            return result
        stack.append(root)
        while len(stack) >0 :
            node = stack.pop()
            if node:
                stack.append(node.left)
                stack.append(node.right)
                result.append(node.value)
        return result[::-1]

非递归遍历的代码和前序遍历的非递归代码乍一看是很相似的,但过程有些难以理解,可以用表格的形式来简单理解下步骤,例如:
这里写图片描述

后面的还有不少,有兴趣的自己可以试验下,加深理解。迭代到最后会发现,while结束时,result中的值恰好是[‘F’,’E’,’G’,’M’,’H’,’C’,’D’,’B’,’A’]。我们知道在一个二叉树的每一个子结构中,后序遍历都是按照左右父的顺序进行的,利用stack可以使得在每一个子结构中,左子率先进栈,待某个父节点右子树全部遍历完后才开始遍历左子树。因此你会发现每一个子结构(这里说的子结构是指只有父节点,左子节点和右子节点的一般二叉树结构),在进入结果列表中时都是按照父节点、右节点、左节点进入,而进入stack辅助栈时是从左往右的,因此最后只要将result反转一下即可。

层次遍历二叉树
层次遍历用非递归的形式比较多,主要是层次遍历的思想类似BFS,递归并不太适合,这里只说一下非递归的形式。

    def levelorderTraversal(self, root):
        result = []
        queue = []
        if root is None:
            return result
        queue.append(root)
        result.append([root.value])
        #第一个while中的queue是变化的,保证是否还有节点未被遍历到
        while len(queue) > 0:
            n = len(queue)
            temp = []
            #这里的n表示的是每一层的节点
            while n:
                node = queue.pop(0)
                if node.left:
                    queue.append(node.left)
                    temp.append(node.left.value)
                if node.right:
                    queue.append(node.right)
                    temp.append(node.right.value)
                n -= 1
            if len(temp) > 0:
                result.append(temp)
        return result

到这里只是简单的说了下有关二叉树的构建遍历等问题,有了这些基本实现,之后会继续针对leetcode上的其他二叉树题目进行总结整理~

版权声明:本文为wolvvi原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/wolvvi/article/details/82052662

智能推荐

说说 Python Django 应用的基础目录结构

通过以下 django-admin 指令创建应用之后,就会生成应用的基础目录结构。 比如,我们建立了一个叫 ‘first’ 的应用,它的目录结构是这样的: 目录或文件 说明 最外层的 first/ 这是新应用的根目录,所有与该应用相关的内容都放在这里。 manage.py 用于管理 Django 项目的命令行工具。 里面一层的 first/ 目录 是一个...

Springboot整合rabbitMQ

依赖: 配置文件application.yml RabbitConfig 消息生产者RabbitProducer 消息消费者RabbitCustomer 通过Controller进行调用 启动项目后调用接口: 结果:...

Thread.join()方法的使用

如果一个线程A执行了thread.join()语句,代表当前线程A等待thread线程终止后才从thread.join()方法返回 并且这个方法具有超时特性,可以添加参数设置 输出结果: jdk中Thread.join()方法的源码(进行了部门调整)   每个线程终止的条件是前驱线程的终止,每个线程等待前驱线程终止后,才从join()方法返回,  当线程终止时,会调用自身的no...

linux服务器部署jenkins笔记

安装jenkins参考文档:https://blog.csdn.net/tomatocc/article/details/83930714 1. 打开jenkins官网:https://jenkins.io/download/ 将war包下载到本地 **ps:**这里要注意的是要下载左边下方的war包,不要下载右边下面的war包。左边是稳定版本,右边是最新版本,建议大家使用稳定版本(我刚开始下载的...

k8s部署elasticsearch集群

百度营销大学     环境准备 我们使用的k8s和ceph环境见: https://blog.51cto.com/leejia/2495558 https://blog.51cto.com/leejia/2499684 ECK简介 Elastic Cloud on Kubernetes,这是一款基于 Kubernetes Operator 模式的新型编排产品,用户可使用该产品在...

猜你喜欢

saas-export项目-AdminLTE介绍与入门

AdminLTE介绍 (1)AdminLTE是什么? AdminLTE是一款建立在bootstrap和jquery之上的开源的模板主题工具 (2)AdminLTE有什么特点? 提供一系列响应的、可重复使用的组件, 并内置了多个模板页面 自适应多种屏幕分辨率,兼容PC和移动端 快速的创建一个响应式的Html5网站 AdminLTE 不但美观, 而且可以免去写很大CSS与JS的工作量 AdminLTE...

MyBatis中ResultMap结果集映射

用于解决属性名和字段名不一致的情况: resultMap 元素是 MyBatis 中最重要最强大的元素。...

编写一个shell

编写shell的过程: 1.从标准输入中读入一个字符串。 2.解析字符串 3.创建一个子进程的执行程序。 4.子进程程序替换。 5.父进程等待子进程退出。...

WEB自动化测试中Xpath定位方法

前言: Xpath是在XML文档中查找信息的一种语言,使用路径表达式来选取XML文档中的节点或节点集,由于XML与HTML结构类似(前者用于传输数据,后者用于显示数据),所以Xpath也常用于查找HTML文档中的节点或节点集。 一  路径表达式: 路径以“/”开始     表示找到满足该绝对路径的元素; 路径以//”开始  ...

力扣困难难度 第4题 寻找两个正序数组的中位数

先看一眼题 我的思路: 设置下标i,j分别用于遍历两个数组,初始值均为0,直到找到两个数组中从小到大的第第length/2个数为止结束循环,length为两个数组长度之和。 ·每次比较nums[i]nums[j],如果前者小则i++,否则j++ ·循环结束时,如果count已经达到length/2,则说明已经找到了中位数,[注意:此时有可能正好其中一个数组遍历完了!所以...