ITPub博客

既然中序和后序队列构成二叉树写了，就把前序和中序一做吧。原理其实也很简单，前序队列第一个点就是根节点，再中序队列里面这个根节点可以分出左右两个树的两个中序队列，然后可以按照左右树的节点数量，再前序节点里面分出对应两组前序队列；然后反复递归即可。# Definition for a binary tree node. # cla

 假期继续刷题，也没有别的什么事情可以干。 这个题是给出中序和后序遍历队列，构造对应二叉树；题目很简单，如下图，给出两个遍历队列，构成二叉树，这里假定没有重复点。 想了好几天，真是惭愧，因为一直想一次遍历就完成构造，最后发现不行；然后就硬搞出一个多重循环的遍历方法，虽然可行，但是提交后提示耗时超过限制。最后还是用递归实现的。 其实原理很简单，对于后续遍历队列

继续刷题，判断二叉树是否存在一条路径满足和值要求。这个名称描述很复杂，其实很简单。如下图，判断是否有一个从根节点到叶子节点路径，和值为8， 就是1 -> 2-> 5。这个用递归来做很简单，就是判断输入节点的值和输入值是否一样，如果是而且当前节点为叶子节点，返回True，如果当前节点为空，返回False; 如果都不是，则递归到输入节点子节点，并且输入值为sum减去当前节点。这里使用or

继续刷题，判断是否镜像对称二叉树。镜像对称二叉树，顾名思义，以根节点为轴，左右节点和节点内容互为镜像；如下图所示。这里要避免和完全二叉树混淆。这个我还是考虑了一段时间，递归和迭代都可以实现。递归的，如果一个节点值作为输入很难实现，所以新建一个新方法recurse，输入左右两个节点，返回bool值。思路很简单，如果输入两个节点都是空，可能是单个跟节点，返回True；如果一个有，另一个为空，返回Fal

继续刷题， Python用递归实现求二叉树深度。其实就是求二叉树层级，比如一个单点就是一层，一个单点加左右两个叶子节点就是两层。其实二叉树问题用递归来求是比较快的。这个也是介绍的默认递归方法，就是如有子节点，递归，直到没有子节点为止。# Definition for a binary tree node. # cla

继续刷题，刷题果然会上瘾。Python实现二叉树按层级遍历，看起来有点复杂。如下图，如果一个二叉树有多层，则从上到下，每层按从左到右遍历。每层放在一个队列，整体返回一个多组队列的队列。看起来复杂，其实实现反而很简单；不用栈，就用一个节点队列放当前层级节点，遍历当前层级节点，读取值放入一个读取队列，读取当前节点的子节点放入另一个队列；当当前队列节点遍历完成后，使用下一层节点对用，相当于进入下一层，遍

顺便把Python用非递归实现二叉树后续遍历也写了。其实前序中序和后续都是针对父节点说的。比如下面这个最简单二叉树。前序就是ABC，父节点A在前中序就是BAC，父节点A在中间后序就是BCA，父节点A在最后无论多复杂二叉树，基本都是同样遍历流程。后续遍历可以说是最简单的，从左开始遍历并放入栈，读取没有下级节点的节点值，然后把该节点推出栈，并删除和上级节点关联；然后替换栈中最上的点，并去遍历右边子节点

刷题没事会上瘾，继续做了非递归中序遍历。中序遍历其实和就是先找到最左边节点，然后是其上级节点，再到上级节点的右边节点。比如下面的中序遍历结果就是 DBEAFC非递归实现逻辑，我想的这个比较笨。就是用一个队列做栈，先按照左边遍历压入栈中；当到左边叶子节点时候，读取并删除关联；推出栈回到上一级节点，如果上级节点没有右节点，则读取继续删除；如果有，则遍历右节点；为了防止右边遍历返回时候再次读取父节点；要

刷刷题换换下脑子。然后去一个刷题网站，从入门开始，没想到python写多了，数据结构都忘了，第一个二叉树前序遍历就想了好久才写出来。这里记录下，也算记录。二叉树前序遍历(Binary Tree Preorder Traversal)， 前序遍历首先访问根结点然后遍历左子树，最后遍历右子树。如下图所示，前序遍历结果：ABDECF考虑了下，要创建两个队列，一个放遍历结果，一个做类似栈作用，把路过节点放