可以访问违规网站的浏览器,西安核心关键词排名,兴义网站开发公司,网络运维必备知识概述
二叉树作为一个基础的数据结构#xff0c;遍历算法作为一个基础的算法#xff0c;两者结合当然是经典的组合了。很多题目都会有 ta 的身影#xff0c;有直接问二叉树的遍历的#xff0c;有间接问的。比如要你找到树中满足条件的节点#xff0c;就是间接考察树的遍历…概述
二叉树作为一个基础的数据结构遍历算法作为一个基础的算法两者结合当然是经典的组合了。很多题目都会有 ta 的身影有直接问二叉树的遍历的有间接问的。比如要你找到树中满足条件的节点就是间接考察树的遍历因为你要找到树中满足条件的点就需要进行遍历。 你如果掌握了二叉树的遍历那么也许其他复杂的树对于你来说也并不遥远了 二叉数的遍历主要有前中后遍历和层次遍历。 前中后属于 DFS层次遍历则可以使用 BFS 或者 DFS 来实现。只不过使用 BFS 来实现层次遍历会容易些因为层次遍历就是 BFS 的副产物啊你可以将层次遍历看成没有提前终止的 BFS。
DFS 和 BFS 都有着自己的应用比如 leetcode 301 号问题和 609 号问题。
DFS 都可以使用栈来简化操作并且其实树本身是一种递归的数据结构因此递归和栈对于 DFS 来说是两个关键点。
DFS 图解 BFS 的关键点在于如何记录每一层次是否遍历完成 我们可以用一个标识位来表式当前层的结束。
对于前中后序遍历来说。首先不管是前中还是后序遍历变的只是根节点的位置 左右节点的顺序永远是先左后右。 比如前序遍历就是根在前面即根左右。中序就是根在中间即左根右。后序就是根在后面即左右根。
下面我们依次讲解
前序遍历
相关问题144.binary-tree-preorder-traversal 前序遍历的顺序是根-左-右
思路是
先将根结点入栈出栈一个元素将右节点和左节点依次入栈重复 2 的步骤
总结 典型的递归数据结构典型的用栈来简化操作的算法。
其实从宏观上表现为自顶向下依次访问左侧链然后自底向上依次访问右侧链如果从这个角度出发去写的话算法就不一样了。从上向下我们可以直接递归访问即可从下向上我们只需要借助栈也可以轻易做到。
整个过程大概是这样
这种思路有一个好处就是可以统一三种遍历的思路. 这个很重要如果不了解的朋友希望能够记住这一点。
中序遍历
相关问题94.binary-tree-inorder-traversal 中序遍历的顺序是 左-根-右根节点不是先输出这就有一点点复杂了。
根节点入栈判断有没有左节点如果有则入栈直到叶子节点 此时栈中保存的就是所有的左节点和根节点。 出栈判断有没有右节点有则入栈继续执行 2
值得注意的是中序遍历一个二叉查找树BST的结果是一个有序数组利用这个性质有些题目可以得到简化 比如230.kth-smallest-element-in-a-bst 以及98.validate-binary-search-tree
后序遍历
相关问题145.binary-tree-postorder-traversal 后序遍历的顺序是 左-右-根 这个就有点难度了要不也不会是 leetcode 困难的 难度啊。
其实这个也是属于根节点先不输出并且根节点是最后输出。 这里可以采用一种讨巧的做法 就是记录当前节点状态如果
当前节点是叶子节点或者当前节点的左右子树都已经遍历过了那么就可以出栈了。
对于 1. 当前节点是叶子节点或者当前节点的左右子树都已经遍历过了那么就可以出栈了。 对于 2. 当前节点的左右子树都已经遍历过了 只需要用一个变量记录即可。最坏的情况我们记录每一个节点的访问状况就好了空间复杂度 O(n) 但是仔细想一下我们使用了栈的结构从叶子节点开始输出我们记录一个当前出栈的元素就好了空间复杂度 O(1) 具体请查看上方链接。
层次遍历
层次遍历的关键点在于如何记录每一层次是否遍历完成 我们可以用一个标识位来表式当前层的结束。 具体做法
根节点入队列 并入队列一个特殊的标识位此处是 null出队列判断是不是 null 如果是则代表本层已经结束。我们再次判断是否当前队列为空如果不为空继续入队一个 null否则说明遍历已经完成我们什么都不不用做如果不为 null说明这一层还没完则将其左右子树依次入队列。
相关问题
双色标记法
我们知道垃圾回收算法中有一种算法叫三色标记法。 即
用白色表示尚未访问灰色表示尚未完全访问子节点黑色表示子节点全部访问
那么我们可以模仿其思想使用双色标记法来统一三种遍历。
其核心思想如下
使用颜色标记节点的状态新节点为白色已访问的节点为灰色。如果遇到的节点为白色则将其标记为灰色然后将其右子节点、自身、左子节点依次入栈。如果遇到的节点为灰色则将节点的值输出。
使用这种方法实现的中序遍历如下
class Solution:def inorderTraversal(self, root: TreeNode) - List[int]:WHITE, GRAY 0, 1res []stack [(WHITE, root)]while stack:color, node stack.pop()if node is None: continueif color WHITE:stack.append((WHITE, node.right))stack.append((GRAY, node))stack.append((WHITE, node.left))else:res.append(node.val)return res可以看出实现上 WHITE 就表示的是递归中的第一次进入过程Gray 则表示递归中的从叶子节点返回的过程。 因此这种迭代的写法更接近递归写法的本质。
如要实现前序、后序遍历只需要调整左右子节点的入栈顺序即可。可以看出使用三色标记法 其写法类似递归的形式因此便于记忆和书写缺点是使用了额外的内存空间。不过这个额外的空间是线性的影响倒是不大。
虽然递归也是额外的线性时间但是递归的栈开销还是比一个 01 变量开销大的。换句话说就是空间复杂度的常数项是不同的这在一些情况下的差异还是蛮明显的。
划重点双色迭代法是一种可以用迭代模拟递归的写法其写法和递归非常相似要比普通迭代简单地多。
Morris 遍历
我们可以使用一种叫做 Morris 遍历的方法既不使用递归也不借助于栈。从而在 O ( 1 ) O(1) O(1) 空间完成这个过程。
如果你需要使用 O ( 1 ) O(1) O(1) 空间遍历一棵二叉树那么就要使用 Morris 遍历。
这个算法考察相对少作为了解即可。
def MorrisTraversal(root):curr rootwhile curr:# If left child is null, print the# current node data. And, update# the current pointer to right child.if curr.left is None:print(curr.data, end )curr curr.rightelse:# Find the inorder predecessorprev curr.leftwhile prev.right is not None and prev.right is not curr:prev prev.right# If the right child of inorder# predecessor already points to# the current node, update the# current with its right childif prev.right is curr:prev.right Nonecurr curr.right# else If right child doesnt point# to the current node, then print this# nodes data and update the right child# pointer with the current node and update# the current with its left childelse:print (curr.data, end )prev.right currcurr curr.left划重点Morris 是一种可以在 O ( 1 ) O(1) O(1) 空间遍历二叉树的算法。
总结
本文详细讲解了二叉树的层次遍历和深度优先遍历。
对于深度优先遍历我们又细分为前中后序三种遍历方式。
最后我们讲解了双色遍历和 Morris 遍历。这两种方式可以作为了解不掌握也没关系。
另外如果题目要求你实现迭代器就是调用一次输出一个二叉树的值那么前面讲的迭代的方式就非常适用了。比如这道题 Binary Search Tree Iterator
