DFA實現(xiàn)迭代遍歷二叉樹(前、中、后)
狀態(tài)機過程詳解
我們定義三個狀態(tài)：
LEFT狀態(tài)：代表左右子樹均未被遍歷
RIGHT狀態(tài)：代表左子樹被遍歷
UP狀態(tài)：代表左右子樹都被遍歷過
注意還需要一個棧用于存儲遍歷路徑，方便拿取父節(jié)點。
實現(xiàn)了這個迭代過程后，我們發(fā)現(xiàn)，實際上
LEFT狀態(tài)就是前序遍歷的操作狀態(tài)，RIGHT狀態(tài)就是中序遍歷的操作狀態(tài)，UP狀態(tài)就是后序遍歷的操作狀態(tài)，自此用迭代實現(xiàn)了遞歸的完全模擬。
畫出狀態(tài)轉(zhuǎn)移圖
(前序遍歷代碼)代碼
這里只展示前序遍歷的代碼，中序和后序也很簡單，直接在對應(yīng)的狀態(tài)取數(shù)值即可。
驗證代碼可以到leetcode平臺：https://leetcode.cn/problems/binary-tree-preorder-traversal/submissions
標簽：
