[Data Structure] 二元樹的追蹤 (Binary Tree Traversal)

定義

追蹤樹中的每一個節點，且每個節點恰好被尋訪一次。

M (Middle): 中間 (指樹根)
L (Left) : 左邊 (指左子樹)
R (Right) : 右邊 (指右子樹)

可能追蹤的順序

1. MLR (前序追蹤)

又稱 深度優先追蹤，也就是先拜訪樹根，然後拜訪左子樹，再拜訪右子樹

2. LMR (中序追蹤)

又稱 對稱追蹤，也就是先拜訪左子樹，然後拜訪樹根，再拜訪右子樹

參考 [Leetcode] 94. Binary Tree Inorder Traversal (二叉樹的中序遍歷)

3. LRM (後序追蹤)

又稱 廣度優先追蹤，也就是先拜訪左子樹，然後拜訪右子樹，再拜訪樹根

規則

"L" 一定要在 "R" 之前追蹤。
亦即左子樹在追蹤之後，才能追蹤右子樹 (Left node always first)

快速記憶

1. 所謂的前序、中序、後序中，前中後代表的是每個二元樹的父節點，所以只要記住父節點的擺放順序，就能快速記憶前中後的排序了
2. 再次強調 "L" 一定要在 "R" 之前追蹤。

只要記住這兩個規則，就可以永遠記得前中後的排序方式了