攻城獅
Not a programmer 不工程的攻城獅

Not a programmer 不工程的攻城獅

Series

Software development

A series about software engineering

Articles in this series

Algorithm 演算法 - 樹遍歷系列 Morris traversal 莫里斯遍歷

May 17, 2022

簡介 Intro 此演算法是由 Joseph M. Morris 在 1979 年的論文「Traversing Binary Trees Simply and Cheaply」首次提出,因此稱之為 -- Morris traversal。其核心概念是利用樹中的空閒指針,縮減空間複雜度到常數。Morris traversal 主要是中序處理,但是修改後也是可以適用於前序和後序。 中序 In-Order 先初始化 root 作為當前節點 curr 當前節點 curr 不是 NULL 的時候,就往左...