樹的遍歷
前言
- 在一個平常的星期二下午，一節資料結構課中，想著做點什么的我，打開了力扣，正好老師在講樹，我也從二叉樹最基礎的遍歷開始刷題，沒想到打開了新世界的大門······
前提知識
- 二叉樹有三種遍歷方式：
- 前序遍歷(根節點 -> 左子樹 -> 右子樹)
- 中序遍歷(左子樹 -> 根節點 -> 右子樹)
- 后序遍歷(左子樹 -> 右子樹 -> 根節點)
- 可以看出這三種遍歷方式的特點：
- 前/中/后，代表著根節點的遍歷順序
- 左子樹一定比右子樹先訪問到
遍歷方法一 ———— 遞回
- 用當時老師的話來說就是：三行代碼的事
- 至于哪三行，話不多說，上代碼：
//LeetCode 144. 二叉樹的前序遍歷
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
void preorder(TreeNode* root, vector<int> &res) {
//遞回退出條件，同時也是“商業程式員”以后作業要注意的錯誤排查
if (root == nullptr) {
return ;
}
res.push_back(root -> val);//輸出當前節點的值，放第一行表示輸出根節點
preorder(root -> left, res);//遍歷左子樹
preorder(root -> right, res);//遍歷右子樹
}
vector<int> preorderTraversal(TreeNode* root) {
vector<int>res;
preorder(root, res);
return res;
}
};
//時間復雜度：O(n)O(n)，其中 nn 是二叉樹的節點數，每一個節點恰好被遍歷一次，
//空間復雜度：O(n)O(n)，為遞回程序中堆疊的開銷，平均情況下為 O(\log n)O(logn)，最壞情況下樹呈現鏈狀，為 O(n)O(n)，
- 同理，若想使用中/后序遍歷，只需將
res.push_back(root -> val);放在第二/第三行即可
遍歷方法二 ———— 迭代
- 由之前的刷題經驗可知，很多能用遞回實作的方法也可以用迭代實作，在此處也是可以的，只不過迭代會比遞回更難理解一些
深入底層
- 為什么能用遞回實作的時候，也能用迭代實作呢？我們不妨想想遞回實作的底層原理是什么，遞回實作遍歷本質上是函式不斷呼叫自身，但通過改變傳入形參來不斷遞進的程序，在這個程序中，遞回隱式地維護了一個堆疊：呼叫preorder并讓其入堆疊，左子樹走到底之后就將元素彈出(輸出元素)，然后遍歷右子樹，由于這個程序太隱蔽了(都是程式運行時內部完成的)，我們就看不到遞回背后的運行情況是怎么樣的(這可能也是遞回難以理解的原因之一)，而迭代其實就是將這個程序展現出來，顯式地維護這個堆疊，完成計算機底層實作的操作，以下是代碼：
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
if (root == nullptr) {
return res;
}
stack<TreeNode*> stk;
TreeNode* node = root;
while (!stk.empty() || node != nullptr) {
while (node != nullptr) {
res.emplace_back(node->val);//前序遍歷，先將根節點輸出
stk.emplace(node);
node = node->left;
}
node = stk.top();
stk.pop();
node = node->right;
}
return res;
}
};
- 一般都是遞回比迭代難理解，但這里似乎是個反例，迭代的代碼比遞回的更復雜難懂一些，但仔細看會發現和遞回其實是一樣的，中/后序遍歷也只需要簡單調整代碼邏輯順序就可以了，
分隔欄：偷個懶下次繼續寫,該去學java了(2022.9.27 19:28)
遍歷方法三 ———— Morris 遍歷
遍歷方法四 ———— 標記遍歷法
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/509690.html
標籤：其他