摘要
- 二叉樹的基礎操作：前序、中序、后序遍歷
- 迭代遍歷性能較遞歸遍歷好，但代碼實現(xiàn)相對復雜
今日學習資料
- 代碼隨想錄 二叉樹
- 數(shù)據(jù)結(jié)構(gòu)C++語言版第二版（清華大學出版社）二叉樹部分
- 王道考研數(shù)據(jù)結(jié)構(gòu)復習指導 二叉樹部分
二叉樹基礎知識
- 二叉樹的節(jié)點的定義
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) {}
};
- 前序、中序、后序的“前”“中”“后”都指的是父節(jié)點相對于其左孩子和有孩子在遍歷順序中的位置。
- 前序、中序、后序的定義不在這里重復，以下以代碼為主。
LeetCode144 二叉樹的前序遍歷
- 遞歸法，最直觀最容易理解的方法，用遞歸隱式維護了一個棧。
class Solution {
public:
void preorderTraversalWorkPlace(TreeNode* node, vector<int>& res) {
if (node == nullptr) {
return;// 遞歸終止條件
}
res.push_back(node->val);
preorderTraversalWorkPlace(node->left, res);
preorderTraversalWorkPlace(node->right, res);
}
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
preorderTraversalWorkPlace(root, res);
return res;
}
};
- 迭代法，前序遍歷的迭代法是最容易實現(xiàn)的，因為在前序遍歷中，對樹的節(jié)點的訪問順序和處理順序是相同的
- 訪問順序：通過cur訪問樹的節(jié)點的順序
- 處理順序：在這里，對樹的節(jié)點的處理是取其中的值到保存遍歷順序的數(shù)組中
- 可以看出，在前序遍歷中，只要
- 不斷地取當前節(jié)點的值保存進答案數(shù)組，并將當前節(jié)點出棧
- 然后嘗試將當前節(jié)點的右孩子和左孩子放入棧中，這里要注意棧的后進先出，前序遍歷需要“中左右”，所以我們讓右孩子先進棧。
- 實際上我們只需要用一個棧和一個臨時保存已經(jīng)彈出的棧頂元素的變量就可以完成前序遍歷。前序遍歷實際上只需要一個棧就可以完成。
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> s;
if (root) {
s.push(root);
}
TreeNode* cur;
while (!s.empty()) {
cur = s.top();
s.pop();
res.push_back(cur->val);
if (cur->right) {
s.push(cur->right);
}
if (cur->left) {
s.push(cur->left);
}
}
return res;
}
};
LeetCode94 二叉樹的中序遍歷
- 遞歸法，由于不需要我們手動維護遞歸棧，遞歸法依然是最直觀，最容易理解的方法
class Solution {
public:
void inorderTraversalWorkPlace(TreeNode* node, vector<int>& res) {
if (node == nullptr) {
return;
}
inorderTraversalWorkPlace(node->left, res);
res.push_back(node->val);
inorderTraversalWorkPlace(node->right, res);
}
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
inorderTraversalWorkPlace(root, res);
return res;
}
};
- 迭代法，這里體現(xiàn)出了中序遍歷和前序遍歷的區(qū)別，即在中序遍歷中，對樹的節(jié)點的訪問順序和處理順序是不同的
- 訪問順序：實際上，我們對二叉樹的訪問順序是基本固定的，即只能從父節(jié)點到左孩子或者右孩子
- 處理順序：但在中序遍歷中，我們要先取出的是左孩子，這自然與訪問順序有差別
- 所以，中序遍歷不能只依靠一個棧來完成，而是要引入一個指針
cur來先訪問左孩子，并將訪問過的左孩子保存在棧中，來調(diào)整對樹的訪問順序。- 用
cur一直訪問向左訪問左孩子，直到左孩子為空，將cur指回當前棧頂?shù)墓?jié)點 - 中序遍歷是“左中右”，既然當前
cur已經(jīng)沒有左孩子或者左孩子已經(jīng)處理過了，當前cur對應的是“中”，自然輪到cur指向的節(jié)點進行處理，然后棧頂元素出棧。 - 接下來輪到
cur的右孩子，所以嘗試讓cur指向cur的右孩子，進入下一輪循環(huán)，嘗試遍歷“右”。
- 用
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> st;
if (!root) {
return res;
}
TreeNode* cur = root;
while (cur || !st.empty()) {
if (cur) {
st.push(cur);
cur = cur->left;
}
else {
cur = st.top();
st.pop();
res.push_back(cur->val);
cur = cur->right;
}
}
return res;
}
};
LeetCode145 二叉樹的后序遍歷
- 遞歸法
class Solution {
public:
void postorderTraversalWorkPlace(TreeNode* node, vector<int>& res) {
if (node == nullptr) {
return;
}
postorderTraversalWorkPlace(node->left, res);
postorderTraversalWorkPlace(node->right, res);
res.push_back(node->val);
}
vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;
postorderTraversalWorkPlace(root, res);
return res;
}
};
-
迭代法，遵守后序遍歷的定義，對內(nèi)存的進行“左右中”的有序訪問
- 和中序遍歷一樣，后序遍歷中，對樹的元素訪問順序和處理順序是不一致的，所以需要引入指針來調(diào)整訪問順序
- 和中序遍歷相比，后序遍歷為“左右中”，沒有左孩子或左孩子已經(jīng)處理完后，還要再訪問一遍“中”才能去處理右孩子。處理完右孩子后，才輪到“中”進入遍歷順序，這意味著，在循環(huán)中會出現(xiàn)對“中”的重復訪問。
- 所以，除了
cur指針外，還要再引入一個pre指針來判斷是否重復訪問某個節(jié)點。
后序遍歷“左右中”
- 先讓
cur一直嘗試往左孩子走，并將cur訪問過的節(jié)點保存在棧中，直到cur指向NULL。此時棧頂保存的節(jié)點沒有左孩子，那么就剩下“右中”需要處理。 - 讓
cur指向棧頂保存的節(jié)點，并讓棧頂節(jié)點出棧。然后處理“右”，如果當前節(jié)點沒有右孩子，或者右孩子已經(jīng)被訪問過，則只剩下“中”，所以已經(jīng)可以將當前節(jié)點加入遍歷序列。 - 要記得將當前節(jié)點保存在
pre中，作為下一個棧頂?shù)墓?jié)點判斷右孩子是否已經(jīng)訪問過的依據(jù)。
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;
if (!root) {
return res;
}
stack<TreeNode*> st;
TreeNode* cur = root;
TreeNode* pre = nullptr;
while (cur || !st.empty()) {
while (cur) {
st.push(cur);
cur = cur->left;
}
cur = st.top();
st.pop();
if (cur->right == nullptr || cur->right == pre) {
res.push_back(cur->val);
pre = cur;
cur = nullptr;
}
else {
st.push(cur);
cur = cur->right;
}
}
return res;
}
};
- 將前序遍歷轉(zhuǎn)化為后序遍歷的迭代法
- 前序遍歷是“中左右”，而后序遍歷是“左右中”，所以
- 調(diào)整前序遍歷中左孩子和右孩子的入棧順序，先將左孩子入棧再將右孩子入棧，此時調(diào)整過的“前序遍歷”為“中右左”
- 再將整個答案數(shù)組反轉(zhuǎn)，就得到了“左右中”
- @Edward Elric 在 LeetCode 的官方題解的評論中指出，這樣的方法只是得到了后序遍歷的序列，但是并沒有真正實現(xiàn)按后序遍歷定義的順序的內(nèi)存訪問。
- 前序遍歷是“中左右”，而后序遍歷是“左右中”，所以
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
stack<TreeNode*> st;
vector<int> res;
if (!root) {
return res;
}
st.push(root);
while (!st.empty()) {
TreeNode* node = st.top();
st.pop();
res.push_back(node->val);
if (node->left) st.push(node->left);
if (node->right) st.push(node->right);
}
reverse(res.begin(), res.end());
return res;
}
};
image.png
- 更深一步的思考，是不是我們在迭代實現(xiàn)的思路中，沒有用棧去很好地模擬函數(shù)的遞歸調(diào)用？順著這個思路，即如何用棧來模擬二叉樹遍歷的遞歸實現(xiàn)，我在另一篇博客中分享了自己的理解。
