[問題] Morris Traversal
看板Prob_Solve (計算數學 Problem Solving)作者FRAXIS (喔喔)時間9年前 (2015/07/20 01:33)推噓0(0推 0噓 0→)留言0則, 0人參與討論串1/1
最近認真的看了一下 Morris traversal 的技巧，可以在 O(n) 時間， O(1) 空間
作 inorder, preorder, 和 postorder traversal。
除了單純 traverse 之外，似乎也可以在 O(1) 空間內找出樹的高度，但是不知道
對不對。（用 DFS 算的話，使用的空間會跟樹高成正比）
我的想法是在執行 Morris preorder traverse 的同時維護當前的高度。
此時有兩個困難點：
1. 判斷葉節點
雖然在 Morris traversal 的過程中樹型會有所變化，
不過在 Morris traversal 中，被建立起來的 thread 指標會導致迴圈，
所以可以藉由這個性質來判斷某個指標是原本的指標還是被創造出來的。
2. Backtracking 時當前高度的維護
這也可以利用 thread 產生的迴圈來計算出應該修正的量。
所以我覺得計算高度或是一些樹上單純 top-down 統計數據的問題，都可以用
O(1) 空間和線性時間來完成。 不知道有沒有人思考過類似的問題？
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 76.118.43.187
※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1437327189.A.2CE.html
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
