二叉树的遍历通常O(n)的时间复杂度与O(logn)的空间复杂度,而morris遍历实现了O(n)的时间复杂度和O(1)的空间复杂度…
morris遍历的原理
对于没有左子树的节点只达到一次,对于有左子树的节点会到达两次;
morris遍历的实现原则
记当前节点为cur
- 如果cur无左子树,cur右移(cur = cur.right);
- 如果cur有左子树,找到cur左子树最右的节点,记做mostright;
- 如果mostright的right指针为空,则将其指向cur(mostright.right = cur),cur左移(cur = cur.left);
- 如果mostright的right指针指向cur,则将其置为空(mostright.right = null),cur右移(cur = cur.right);
图示:
代码实现
1 | /** |
补充思考
1、为什么morris遍历的空间复杂度为O(1),而一遍的遍历为O(logN)呢?怎么计算的?
一般二叉树的遍历:
- 先序遍历:按照
父节点 -> 左孩子 -> 右孩子
的顺序遍历,与DFS(深度优先搜索)有一定联系;- 中序遍历:按照
左孩子 -> 父节点 -> 右孩子
的顺序遍历。当二叉树为二叉搜索树时,中序遍历返回结果为有序序列,因此也叫顺序遍历;- 后序遍历:按照
左孩子 -> 右孩子 -> 父节点
的顺序遍历。- 层次遍历:从左到右,一层一层遍历整个树,与BFS(广度优先搜索)有一定联系。
比如我们用栈来完成一个二叉树的先序遍历,通常是这样:
1 | public void preOrderTraversal(TreeNode root) { |
如果二叉树的结构如图所示,那么栈的大小只要能容纳两个节点就够了,所以这种方法的空间复杂度与二叉树的深度有关,最好和平均为O(logN),最坏为O(N);
而Morris遍历却不一样,它通过对子节点引用的更改来实现后续节点的保存,所以仅仅通过O(1)的空间复杂度实现了二叉树的遍历(大神就是不一样…)
参考文档
1、力扣501题解
2、经典算法小评