三種基本遍歷（遞歸版）
void preorder_iter(TreeNode* root) {
stack<TreeNode*> st;
TreeNode* p = root;
while (p || !st.empty()) {
if (p) {
visit(p);
st.push(p);
p = p->left;
} else {
p = st.top(); st.pop();
p = p->right;
}
}
}
中序遍歷
// 標記法：tag=0 表示左子樹返回，tag=1 表示右子樹返回
void postorder_iter(TreeNode* root) {
stack<TreeNode*> st;
stack<int> tag;
TreeNode* p = root;
while (p || !st.empty()) {
while (p) {
st.push(p);
tag.push(0);
p = p->left;
}
if (!st.empty()) {
if (tag.top() == 1) {
p = st.top(); st.pop();
visit(p);
tag.pop(); // 同步彈出
} else {
p = st.top();
p = p->right;
tag.pop();
tag.push(1);
}
}
}
}
線索二叉樹：利用空指針存儲前驅/後繼
節點結構
ThreadNode* pre = nullptr;
void inorder_thread(ThreadNode* p) {
if (!p) return;
inorder_thread(p->left);
if (!p->left) { p->ltag = 1; p->left = pre; }
if (pre && !pre->right) { pre->rtag = 1; pre->right = p; }
pre = p;
inorder_thread(p->right);
}
查找後繼/前驅
void traverse_thread(ThreadNode* root) {
ThreadNode* p = root;
while (p->ltag == 0) p = p->left; // 最左節點
while (p) {
visit(p);
p = inorder_succ(p);
}
}
總結對比
| 方法 | 時間 | 空間 | 適用場景 |
|---|
| 遞歸 | O(n) | O(h) 棧 | 代碼簡潔，樹高受限 |
| 顯式棧 | O(n) | O(h) | 避免棧溢出，可控流程 |
| 線索化 | O(n) | O(1) 額外 | 頻繁遍歷，無修改需求 |
