我想知道是否可以在不使用遞回或堆疊的情況下洗掉具有 O(1) 額外記憶體的二叉樹。
我設法撰寫了樸素的遞回后序遍歷解決方案（使用堆疊記憶體）：
void deleteTreeRec(Node *root)
{
if (root == NULL) return;
deleteTreeRec(root->left);
deleteTreeRec(root->right);
cout << "Deleting node " << root->data << endl;
delete root;
}
我聽說這可以使用（中序）莫里斯遍歷來實作，這似乎是錯誤的，或者至少是違反直覺的，因為據我所知，樹洗掉需要以后序方式遍歷（首先洗掉兩個子樹，然后才是根）。但是，我還沒有找到解決方案的任何詳細描述/偽代碼，因此我在這里試試運氣。
如果有人可以對這個問題有所了解，將不勝感激。謝謝！
uj5u.com熱心網友回復：
在洗掉程序中，二叉樹的現有節點可以用作單鏈表：總是使用left“鏈接”的節點被視為鏈表。
要洗掉所有節點，只需重復以下步驟：
- 找到“鏈表”的尾部
- 如果
right為非空，則將其移至“串列”的末尾 - 將指標存盤在臨時“串列”中的下一個元素
- 如果“串列”非空，則用臨時替換舊頭并重復
開始為在演算法上一尾結果新的尾部運行搜索O(n)，其中n在二叉樹結點的數量。
void deleteTree(Node* root)
{
Node* tail = root;
while (root != nullptr)
{
// update tail
while (tail->left != nullptr)
{
tail = tail->left;
}
// move right to the end of the "list"
// needs to happen before retrieving next, since the node may only have a right subtree
tail->left = root->right;
// need to retrieve the data about the next
Node* next = root->left;
delete root;
root = next;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/344367.html
上一篇：演算法題：給定一個陣列`A`，你可以從中洗掉任何長度為`k`和`??tar`的子陣列。輸出是否可以將`A`設為空
下一篇：計算尺寸等級