摘要：关于二叉树的遍历，使用栈递归或者仿栈循环都是需要的空间，保证了空间为，时间还是比原来多了一遍。思路对每一个节点，优先找到一个节点，这个节点的作用是，当后续节点遍历到这个位置时，可以直接通过这个节点返回它需要返回的位置。
关于二叉树的遍历，使用栈递归或者仿栈循环都是需要O(N)的空间，Morris Traversal保证了空间为O(1)，时间还是O(N)（比原来多了一遍）。
这里只介绍inOrder顺序。
思路：
对每一个cur节点，优先找到一个pre节点，这个pre节点的作用是，当后续cur节点遍历 到这个位置时，可以直接通过这个pre节点返回它需要返回的位置。
例如：
6
/
4 8
/
2 5
上面当cur节点在6的时候，pre节点会在5，因为后面当cur节点遍历到5的时候，可以通过pre节点直接返回6
当cur节点再4的时候，pre节点会在2，当后面cur到2的时候，可以直接返回4
pre找到了，是通过什么返回呢，因为不能修改二叉树结构，也不能使用堆栈记录。
通过mirror(镜像)，也就是说，当找到pre的时候（每个pre的右节点确保为null），在它的右节点创建一个镜像节点，
这个镜像节点直接指向当前的cur节点。
这个操作是不占用空间的，因为只是互相引用。
例如：当上面的cur为6，pre为5，那么设置pre.right=cur，感觉上是这样：
6
/
4 8
/
2 5
6
/
4 8
...
其实并没有多出来那一块，只是5引用到6罢了
6
/ ↑
4 ↑ 8
/ ↑
2 5
理解了这些，那么后续就简单了，当cur遍历到pre的时候并且打印后，将pre新增的引用删除恢复原来的树便可。
代码：
function morrisTraversal(root){
let cur=root,pre
while(cur!=null){
// 当左为空，直接打印
if(cur.left==null){
console.log(cur.val)
cur=cur.right
}else{
// 当左不为空，先去找 pre
pre=cur.left
while(pre.right!=null && pre.right!==cur){
pre=pre.right
}
// 建立引用，用于返回
if(pre.right==null){
pre.right=cur
cur=cur.left
}else{
// 删除引用
console.log(cur.val)
pre.right=null
cur=cur.right
}
}
}
}
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/100846.html
摘要：递归解法由于层次遍历的递归解法不是主流，因此只介绍前三种的递归解法前序遍历递归递归中序遍历递归递归后序遍历递归递归三种递归遍历的总结递归终止的条件为碰到空节点。 目录 分析二叉树的前序，中序，后序的遍历步骤 1.层序遍历 方法一：广度优先搜索 (以下解释来自leetcode官方题解) 方法...
摘要：解法一中序遍历分析由于给定了二叉搜索树，因此首先考虑中序遍历，使用示例，我们先来分别看一下二叉搜索树和累加树中序遍历的结果二叉搜索树二叉累加树。这里还是使用示例，我们再来观察一下二叉搜索树和累加树中序遍历的结果二叉搜索树二叉累加树。 ...
阅读 1175·2021-11-23 10:10
阅读 1498·2021-09-30 09:47
阅读 886·2021-09-27 14:02
阅读 2966·2019-08-30 15:45
阅读 3019·2019-08-30 14:11
阅读 3609·2019-08-29 14:05
阅读 1819·2019-08-29 13:51
阅读 2205·2019-08-29 11:33
