資訊專欄INFORMATION COLUMN
摘要：關于二叉樹的遍歷，使用棧遞歸或者仿棧循環都是需要的空間，保證了空間為，時間還是比原來多了一遍。思路對每一個節點，優先找到一個節點，這個節點的作用是，當后續節點遍歷到這個位置時，可以直接通過這個節點返回它需要返回的位置。
關于二叉樹的遍歷，使用棧遞歸或者仿棧循環都是需要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
}
}
}
}
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/100846.html
摘要：遞歸解法由于層次遍歷的遞歸解法不是主流，因此只介紹前三種的遞歸解法前序遍歷遞歸遞歸中序遍歷遞歸遞歸后序遍歷遞歸遞歸三種遞歸遍歷的總結遞歸終止的條件為碰到空節點。 目錄 分析二叉樹的前序，中序，后序的遍歷步驟 1.層序遍歷 方法一：廣度優先搜索? (以下解釋來自leetcode官方題解) 方法...
摘要：解法一中序遍歷分析由于給定了二叉搜索樹，因此首先考慮中序遍歷，使用示例，我們先來分別看一下二叉搜索樹和累加樹中序遍歷的結果二叉搜索樹二叉累加樹。這里還是使用示例，我們再來觀察一下二叉搜索樹和累加樹中序遍歷的結果二叉搜索樹二叉累加樹。 ...
閱讀 1177·2021-11-23 10:10
閱讀 1499·2021-09-30 09:47
閱讀 887·2021-09-27 14:02
閱讀 2967·2019-08-30 15:45
閱讀 3020·2019-08-30 14:11
閱讀 3610·2019-08-29 14:05
閱讀 1820·2019-08-29 13:51
閱讀 2206·2019-08-29 11:33
