- 博客(2)
- 收藏
- 关注
RSS订阅原创 二叉树的中序遍历
morris遍历是通过记录下左子树的最右节点(morrisRight)到根节点(cur)的关系，从而避免了递归。如何知道这个关系呢？我们会对每个节点进行2次访问，可以在第一次访问时记录下来(morrisRight.Right=cur)，第二次访问时还原节点(morrisRight.Right=nil)，第二次访问时就可以直接回到根节点继续往右遍历。最常见的中底遍历方法为递归遍历，空间复杂度最差情况下为o(n)（取决于栈的深度，二叉树场景下最大深度为n，即一条链，每个节点都只有一个字节点）。
2025-03-22 14:45:40
198
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人