二叉樹的遞歸遍歷

首先需要明確的一點是，前序中序和后序在二叉樹的遞歸遍歷中的區別僅在于遞歸函數中操作的順序，前序是在遍歷一個節點的左右子樹前進行操作，中序是在遍歷一個節點的左子樹后進行操作再遍歷右子樹，而后序是在遍歷完左右子樹再進行操作。所以在遞歸函數中，僅是順序的差別。前序中序和后序可簡化為中左右、左中右和左右中，此外，寫遞歸函數時，需要明確三點：

• 確定遞歸函數的參數和返回值
• 確定終止條件
• 確定單層遞歸的邏輯

? ? ? ? 在對二叉樹的遞歸遍歷中，遞歸函數需要傳入樹節點TreeNode * cur和vec數組進行操作，無實際返回值，所以函數為void，當遞歸操作時，若節點為空則返回，對每層遞歸的邏輯以前序遍歷來說，先講當前節點的val值傳入數組vec中，之后遍歷左子樹，再之后遍歷右子樹。

代碼隨想錄 (programmercarl.com)二叉樹的遞歸遍歷https://programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E9%80%92%E5%BD%92%E9%81%8D%E5%8E%86.html#%E6%80%9D%E8%B7%AF看到遞歸就暈？帶你理解遞歸的本質！_嗶哩嗶哩_bilibilihttps://www.bilibili.com/video/BV1UD4y1Y769/?spm_id_from=333.880.my_history.page.click&vd_source=fc4a6e70e3a87b7ea67c2024e326e7c5

前序遍歷遞歸函數如下所示，

void traversal(TreeNode * cur, vector<int> & vec){//創建前序遞歸遍歷函數if(cur == nullptr)//當當前遍歷節點為空時，返回return;vec.push_back(cur->val);//中 將當前遍歷節點的val值存入vec數組 *操作traversal(cur->left,vec);//遍歷左子樹traversal(cur->right,vec);//遍歷右子樹}void traversal(TreeNode * cur, vector<int> & vec){//創建中序遞歸遍歷函數if(cur == nullptr)//當當前遍歷節點為空時，返回return;traversal(cur->left,vec);//遍歷左子樹vec.push_back(cur->val);//中 將當前遍歷節點的val值存入vec數組 *操作traversal(cur->right,vec);//遍歷右子樹}void traversal(TreeNode * cur, vector<int> & vec){//創建后序遞歸遍歷函數if(cur == nullptr)//當當前遍歷節點為空時，返回return;traversal(cur->left,vec);//遍歷左子樹traversal(cur->right,vec);//遍歷右子樹vec.push_back(cur->val);//中 將當前遍歷節點的val值存入vec數組 *操作}

對于主函數體，只需傳入節點，在函數體中創建一個ans數組，并傳入traversal函數中。

vector<int> preorderTraversal(TreeNode* root) {vector<int> ans;traversal(root,ans);return ans;}

遞歸遍歷樹節點的時間復雜度和空間復雜度均為O(n)。

二叉樹的迭代遍歷

前序遍歷

? ? ? ? 考慮前序遞歸遍歷的過程，若操作為打印，則先將自身val值打印后，對所有左子樹打印，然后打印右子樹，考慮使用棧來模擬前序遍歷的過程（也是用棧來模擬遞歸的過程），由于棧是先入后出的數據結構，前序遍歷結果左子樹節點在右子樹節點前，所以需先對右子樹中節點入棧，再對左子樹中節點入棧。然后是大致流程，創建結果數組ans，先判斷根節點是否為空，若為空直接返回結果數組，否則將根節點入棧，在一個while循環中實現二叉樹的迭代前序遍歷，由于棧模擬的遞歸過程，當棧為空時，也就意味著遞歸結束，即我們遍歷結果結果結束。所以while的循環條件為stack.size()!=0，在循環體內，創建一個指針指向當前節點，將其val值加入ans數組，之后再彈出棧，（第一次循環的pop為根節點，即第一次前序遍歷要對根節點進行操作，之后因為我們是對棧是先加入右子樹節點后加入左子樹節點，所以會先對節點的左子樹進行操作后對節點的右子樹進行操作，完成前序遍歷的過程），之后判斷右子樹的存在，若存在，將其入棧，判斷左子樹的存在，存在則將其入棧，這就是循環體內內容。

class Solution {
public:vector<int> preorderTraversal(TreeNode* root) {stack<TreeNode*> stack;vector<int> ans;if(root == nullptr){//當根節點為nullptr，直接返回ansreturn ans;}stack.push(root);while(stack.size()!=0){//棧不為空則循環TreeNode*cur = stack.top();//創建cur指針指向棧頂地址ans.push_back(cur->val);//將棧頂地址的值存入ans數組stack.pop();//出棧if(cur->right)//判斷左右子樹存在的情況，若存在，將其存入棧中，注意順序，先右后左                //出棧則為先左后右stack.push(cur->right);if(cur->left)stack.push(cur->left);}return ans;}
};

該算法的時間復雜度和空間復雜度均為O(n)。

中序遍歷

? ? ? ? 在遍歷二叉樹的節點時，創建遍歷指針cur，先遍歷左子樹，依次將所有左節點全部入棧，當當前節點的左節點為空時，彈出棧中元素給遍歷指針cur，并將cur指向的val傳入數組中，完成中的操作，令cur = cur->right，并繼續進行循環。算法的時間和空間復雜度均為O(n)。

class Solution {
public:// 定義一個函數，用于執行中序遍歷vector<int> inorderTraversal(TreeNode* root) {// 創建一個空向量 ans，用于存儲遍歷的結果vector<int> ans;// 創建一個空棧 st，用于輔助遍歷stack<TreeNode*> st;// 創建一個指針 cur，初始指向根節點TreeNode* cur = root;// 當 cur 指向的節點不為空或者棧 st 不為空時，進行循環while (cur != nullptr || !st.empty()) {// 如果 cur 指向的節點不為空，則將其壓入棧 st 中，并移動 cur 指針到其左子節點if (cur != nullptr) {st.push(cur);cur = cur->left;}// 如果 cur 指向的節點為空，說明左子節點已經訪問完畢，此時從棧 st 中彈出最上面的節點else {cur = st.top(); // 獲取棧頂節點st.pop(); // 彈出棧頂節點// 將彈出的節點的值添加到 ans 向量中ans.push_back(cur->val);// 移動 cur 指針到其右子節點cur = cur->right;}}// 循環結束后，返回存儲遍歷結果的 ans 向量return ans;}
};

后序遍歷

????????考慮前序遍歷和后序遍歷的相似之處，調整一下前序遍歷中左右節點的入棧順序，讓中左右變為中右左，之后再通過一個reverse即能實現后序遍歷。

調整

//前序
if(cur->right)//判斷左右子樹存在的情況，若存在，將其存入棧中，注意順序，先右后左                //出棧則為先左后右
stack.push(cur->right);
if(cur->left)
stack.push(cur->left);//后序
if(cur->left)
stack.push(cur->left);
if(cur->right)
stack.push(cur->right);

整體代碼

class Solution {
public:vector<int> postorderTraversal(TreeNode* root) {stack<TreeNode*> stack;vector<int> ans;if(root == nullptr){//當根節點為nullptr，直接返回ansreturn ans;}stack.push(root);while(stack.size()!=0){//棧不為空則循環TreeNode*cur = stack.top();//創建cur指針指向棧頂地址ans.push_back(cur->val);//將棧頂地址的值存入ans數組stack.pop();//出棧if(cur->left)stack.push(cur->left);if(cur->right)stack.push(cur->right);}reverse(ans.begin(),ans.end());//反轉return ans;}
};

二叉樹的統一迭代法

周末再看看

代碼隨想錄 (programmercarl.com)二叉樹的統一迭代法https://programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E7%BB%9F%E4%B8%80%E8%BF%AD%E4%BB%A3%E6%B3%95.html#%E6%80%9D%E8%B7%AF