手撕二叉樹遍歷（前序 + 中序 + 后序 遞回 + 非遞回 代碼實作 + 例題）

前引

剛剛才寫完了手撕最小堆的博客 就想了 是不是也得寫一下二叉樹遍歷呢 哈哈 因為前段時間才寫過 而且那個時候理解花了很多時間 所以現在手撕了三個遍歷 大概花了5分鐘左右 力扣三道題 前中后序遍歷也就一次性全部AC啦 把這篇寫了 我就去吃晚飯了惹 那進入下面的題目吧

手撕資料結構 總結博客鏈接

手撕資料結構（最小堆 + 二叉樹前中后非遞回遍歷 + 快排歸并排序 + KMP匹配演算法 + AVL + 紅黑樹）

二叉樹遍歷介紹

二叉樹 真的是經典的不能再經典 對于其三個 非遞回的遍歷 必須熟練熟練的掌握！ 面試肯定是非常常考的 肯定不會考你遞回的 那不然也太弱智了哈哈

二叉樹遍歷 首先需要先搞清楚 什么是前序 什么是中序 什么是后序 我們后面都會用到這張圖 分別再將 這里就先不說了
遍歷當然不僅僅是需要用在二叉搜索樹 任意的樹都可以遍歷 但是對于二叉搜索樹的前中后序遍歷的話 就有一些其他的性質了 這個后面再說

1、二叉樹前序遍歷

在講代碼實作前 我們把上面的前序的結果給出來


我們可以理解 我們最偏向于先輸出值 然后其次是向左節點移動 最后向右節點移動 每當移動后 我們又會按照這個順序進行動作

1、二叉樹前序遍歷代碼（遞回）

作為最經典的遞回實作 遞回代碼如下

class Solution {
public:
    void preorder_visit(TreeNode* root,vector<int>& ret)
    {
        if(!root)   return;
        ret.emplace_back(root->val);
        preorder_visit(root->left,ret);
        preorder_visit(root->right,ret);
    }

    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> ret;
        preorder_visit(root,ret);
        return ret;
    }
};

2、二叉樹前序遍歷代碼（非遞回）

感覺我講怎么非遞回 也不好講
我是以一種抽象的具象化來寫的代碼
我認為就是 前序的話 我們每當訪問到一個節點時 即刻放入陣列中
而遍歷到最左邊的時候 看是否有右邊的結點 如果有 再進入回圈 沒有的話 也無所謂 當前指標等于nullptr 進入下一輪回圈即可

大家還是結合代碼理解一下吧

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        TreeNode* ptr = root; 
        stack<TreeNode*> stack;
        vector<int> ret;

        while(ptr || stack.size())
        {
            while(ptr)
            {
                stack.emplace(ptr);        //放入指標
                ret.emplace_back(ptr->val);//即刻放入
                ptr = ptr->left;		 
            }
            
            ptr = stack.top()->right; //訪問頂部的右邊指標
            stack.pop();			  //已經用過了 則直接pop
        }
        return ret;
    }
};

2、二叉樹中序遍歷

一樣的為了大家方便理解 還是花點時間我自己再做一下中序遍歷的結果


中序遍歷的話 我們還是直接看下面的代碼吧 大家跟著這個圖一起理解

1、二叉樹中序遍歷代碼（遞回）

直接給代碼了

class Solution {
public:
    void inorder_visit(TreeNode* root,vector<int>& ret)
    {
        if(!root)   return;
        inorder_visit(root->left,ret);
        ret.emplace_back(root->val);
        inorder_visit(root->right,ret);
    }

    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ret;

        inorder_visit(root,ret);
        return ret;
    }
};

2、二叉樹中序遍歷代碼（非遞回）

這部分我還是花點時間來寫吧
我的理解是 我們還是跟著遞回代碼來寫
首先 不再是遇到節點就push數字了 而是從stack順著遞回的順序來push 如果是從stack里面出來的再push 然后ptr還是一樣的 從stack.top()->right沒變 變得只是 push數字的順序

代碼實作如下

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        TreeNode* ptr = root; 
        stack<TreeNode*> stack;
        vector<int> ret;

        while(ptr || stack.size())
        {
            while(ptr)
            {
                stack.emplace(ptr); //儲存指標
                ptr = ptr->left;  
            }
            
            ptr = stack.top();   //倒出來指標
            stack.pop();		 //用過了
            ret.emplace_back(ptr->val); // 把值再放進去 按照遞回順序
            ptr = ptr->right;			// 看看右邊指標
        }
        return ret;
    }
};

3、二叉樹后序遍歷

老樣子 放一下后序遍歷結果圖

1、二叉樹后序遍歷代碼（遞回）

直接放代碼了

class Solution {
public:
    void postorder_visit(TreeNode* root,vector<int>& ret)
    {
        if(!root)   return;
        postorder_visit(root->left,ret);
        postorder_visit(root->right,ret);
        ret.emplace_back(root->val);
    }

    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> ret;
        postorder_visit(root,ret);

        return ret;
    }
};

2、二叉樹后序遍歷代碼（非遞回）

后序相對 前序與中序就不一樣了一點 也要難了一點 但是只是有那么一點不同 因為我們需要直到是否當前節點已經被用盡了
對 我是這樣理解的 用盡了 必須要求右邊節點在當前節點前被push進入陣列 如果前一個右邊指標不是pre指標 那么說明右邊要不就是nullptr 如果是空指標 則我們可以直接推入陣列了 因為說明當前這個指標已經是最后一個了
我理解的代碼 也就是這樣寫的 寫出來就是如下 不是很好理解 希望大家多花點時間理解以下代碼

那最后一個就直接放代碼了

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        TreeNode* ptr = root,*pre = nullptr; \\pre指標 記錄前一個被推入陣列 
        stack<TreeNode*> stack;
        vector<int> ret;

        while(ptr || stack.size())
        {
            while(ptr)
            {
                stack.emplace(ptr);
                ptr = ptr->left;
            }
            
            ptr = stack.top();
            if(!ptr->right || ptr->right == pre) //如果右邊指標為空 或者右邊已經被推入了 則可以直接推入
            {
                ret.emplace_back(ptr->val);
                pre = ptr;
                stack.pop();
                ptr = nullptr;
            }
            else    ptr = ptr->right;
        }
        return ret;
    }
};

二叉樹遍歷例題

下面就放三個 經典前中后序的力扣題目 大家也可以去通過這三道題目去驗證自己的代碼是否正確 終于寫完了 現在正在EDG打DK 我得趕快寫了 回寢室看比賽了 太激動了 先寫到這里

144. 二叉樹的前序遍歷
94. 二叉樹的中序遍歷
145. 二叉樹的后序遍歷

Love 6 刷題記錄博客 144. 二叉樹的前序遍歷 （迭代 遞回 Morris）
Love 6 刷題記錄博客 94. 二叉樹的中序遍歷
Love 6 刷題記錄博客 145. 二叉樹的后序遍歷（神級Morris）