二叉樹遍歷的三種方法的非遞歸版本

二叉樹遍歷雖然是一個老生常談的問題，但在面試中經(jīng)常遇見，最近在刷leetcode的時候碰到了用前序，中序和后序遍歷二叉樹，遂來總結(jié)一下思路。

前序遍歷

題目參考leetcode 144 Binary Tree Preorder Traversal

從根節(jié)點出發(fā)，按照根->左子樹->右子樹的順序遞歸訪問整個二叉樹。

例如：輸入 [1,2,3,null,4,5,null]，輸出 [1,2,4,3,5]（可自行畫圖體會）

遞歸版本

代碼十分好寫，思路就是在遞歸訪問左右子樹之前先訪問根節(jié)點

// 定義樹節(jié)點
struct TreeNode{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x):val(x),left(NULL),right(NULL){}
};

// 遞歸函數(shù)，將前序遍歷的結(jié)果放入result中
void preorderCore(TreeNode* pNode,vector<int>& result){
    if(pNode == NULL){
        return;
    }
    result.push_back(pNode->val);
    preorderCore(pNode->left, result);
    preorderCore(pNode->right, result);
}

// 主函數(shù)
vector<int> preorderTraversal(TreeNode* root) {
    if(root == NULL){
        return {};
    }
    vector<int> result;
    preorderCore(root, result);
    return result;
}

非遞歸版本

實際上前序遍歷的非遞歸代碼是三種遍歷方式中最好寫的一個。

思路：使用一個棧保存待訪問的節(jié)點，使用pCur保存當(dāng)前正在訪問的節(jié)點，大致思路和DFS遍歷很類似，就是一路沿左子樹向下，直到左子節(jié)點為空再通過棧進行回退操作，直到棧為空，詳細(xì)代碼如下：

vector<int> preorderTraversal(TreeNode* root) {
    if(root == NULL){
        return {};
    }
    vector<int> result;
    stack<TreeNode*> nodes;
    TreeNode* pCur = root;
    while(!nodes.empty() || pCur != NULL){
        if(pCur != NULL){
            nodes.push(pCur);
            result.push_back(pCur->val);
            pCur = pCur->left;
        }
        else{
            TreeNode* tmp = nodes.top();
            nodes.pop();
            pCur = tmp->right;
        }
    }
    return result;
}

上面的代碼是我認(rèn)為最簡潔的代碼，而且這個利用DFS遍歷二叉樹的模板套路只要略加修改就可以應(yīng)用到剩下的兩個遍歷中。

中序遍歷

題目參考leetcode 94 Binary Tree Inorder Traversal

從根節(jié)點出發(fā)，按左子樹->父節(jié)點->右子樹的順序遞歸訪問。

例如：輸入 [1,2,3,null,4,5,null]，輸出 [2,4,1,5,3]（可自行畫圖體會）

遞歸版本

同樣非常好寫，把握訪問順序即可，代碼如下：

// 樹節(jié)點定義如前序遍歷中定義的一樣
void inorderCore(TreeNode* pNode,vector<int>& result){
    if(pNode == NULL){
        return;
    }
    inorderCore(pNode->left, result);
    result.push_back(pNode->val);
    inorderCore(pNode->right, result);
}

vector<int> inorderTraversal(TreeNode* root) {
    vector<int> result;
    if(root == NULL){
        return result;
    }
    inorderCore(root, result);
    return result;
}

非遞歸版本

如上面所說，可以把前序遍歷的非遞歸代碼略加修改應(yīng)用到這里即可，實際上就是修改了將節(jié)點加入結(jié)果數(shù)組的順序，代碼如下：

vector<int> inorderTraversal(TreeNode* root) {
    vector<int> result;
    if(root == NULL){
        return result;
    }
    stack<TreeNode*> nodes;
    TreeNode* pCur = root;
    while(!nodes.empty() || pCur != NULL){
        if(pCur != NULL){
            nodes.push(pCur);
            pCur = pCur->left;
        }
        else{
            TreeNode* tmp = nodes.top();
            result.push_back(tmp->val);
            nodes.pop();
            pCur = tmp->right;
        }
    }
    return result;
}

后序遍歷

題目參考leetcode 145 Binary Tree Postorder Traversal

從根節(jié)點出發(fā)，按左子樹->右子樹->父節(jié)點的順序遞歸訪問。

例如：輸入 [1,2,3,null,4,5,null]，輸出 [4,2,5,3,1]（可自行畫圖體會）

遞歸版本

同樣按照訪問順序直接寫即可：

// 樹節(jié)點定義同上
void postorderCore(TreeNode* pNode,vector<int>& result){
    if(pNode == NULL){
        return;
    }
    postorderCore(pNode->left, result);
    postorderCore(pNode->right, result);
    result.push_back(pNode->val);
}

vector<int> postorderTraversal(TreeNode* root) {
    if(root == NULL){
        return {};
    }
    vector<int> result;
    postorderCore(root, result);
    return result;
}

非遞歸版本

可以說后序遍歷的非遞歸代碼是三個里面最難的一個，不過按照上面的套路來其實也不難。

注意坑點：由于父節(jié)點需要最后一個彈出，所以如果照搬前面的思路是會出現(xiàn)死循環(huán)的，即重復(fù)訪問父節(jié)點和它的子樹，當(dāng)棧頂元素是某個父節(jié)點時我們并不知道它的孩子沒有沒有被訪問過，會重復(fù)的將它的孩子們壓入棧彈出棧，重復(fù)訪問，解決辦法為使用一個指針lastVisited記錄最后訪問的節(jié)點，當(dāng)棧頂元素為父節(jié)點時，判斷l(xiāng)astVisited是否是它的右節(jié)點，如果是，則代表它的孩子們已經(jīng)遍歷過，直接彈出該父節(jié)點即可，具體代碼如下：

vector<int> postorderTraversal(TreeNode* root) {
    if(root == NULL){
        return {};
    }
    vector<int> result;
    stack<TreeNode*> nodes;
    TreeNode* pCur = root;
    TreeNode* lastVisited = NULL;
    while(!nodes.empty() || pCur != NULL){
        if(pCur != NULL){
            nodes.push(pCur);
            pCur = pCur->left;
        }
        else{
            TreeNode* tmp = nodes.top();
            if(tmp->right != NULL && lastVisited != tmp->right){
                pCur = tmp->right;
            }
            else{
                result.push_back(tmp->val);
                nodes.pop();
                lastVisited = tmp;
            }
        }
    }
    return result;
}

不得不提一下，很多人用前序遍歷的結(jié)果reverse一下作為后序遍歷的答案，雖然結(jié)果是正確的，但是這其實是一種欺騙做法，并沒有按照后序遍歷應(yīng)用的順序訪問節(jié)點啊，攤手。

總結(jié)

實際上這三種遍歷方式的非遞歸算法都遵循了某一規(guī)律，只要熟悉了遍歷順序，寫出代碼也不是很難~希望看完這篇文章能對大家理解二叉樹的遍歷有一點幫助。