15 二叉樹的後序周遊（Binary Tree Postorder Traversal）

目錄

• ​​1 題目​​
• ​​2 描述​​
• ​3 解決方案​

• ​3.1 遞歸算法​

• ​3.1.1 周遊法（Traverse）​

• ​​思路​​
• ​​源碼​​

• ​3.1.2 分治法（Devide And Conquer）​

• ​3.2 非遞歸算法​

• ​3.2.1 二叉樹周遊的非遞歸通用解法​

• ​​圖解​​

• ​​3.3 時間複雜度​​
• ​​3.4 空間複雜度​​

1 題目

  二叉樹的後序周遊（Binary Tree Postorder Traversal）

lintcode：題号——68，難度——easy

2 描述

  給出一棵二叉樹，傳回其節點值的後序周遊。

名詞：

周遊

按照一定的順序對樹中所有節點進行通路的過程叫做樹的周遊。

後序周遊

在二叉樹中，首先周遊左子樹，然後周遊右子樹，最後通路根結點，在周遊左右子樹時，仍然采用這種規則，這樣的周遊方式叫做二叉樹的後序周遊。

序列化規則：

使用大括号包裹節點序列來表示二叉樹，首個資料為根節點，後面接着是其左兒子和右兒子節點值，"#"表示不存在該子節點，之後以此類推。

樣例1：

輸入：二叉樹 = {1,2,3}

輸出：[2,3,1]

解釋：上述{1,2,3}序列按照序列化規則表示的二叉樹如下

1
    / \
   2   3
      

按照後序周遊規則，先左右子樹再根，順序為[2,3,1]

樣例2：

輸入：二叉樹 = {1,#,2,3}

輸出：[1,3,2]

解釋：上述{1,#,2,3}序列按照序列化規則表示的二叉樹如下

1
      /   \
    #       2
           /
          3
      

按照後序周遊規則，先左右子樹再根，順序為[3,2,1]

3 解決方案

  後序周遊與​​前序周遊​​​​[1]​​、​​中序周遊​​​​[2]​​一樣可以使用遞歸和非遞歸兩類方式，遞歸和非遞歸各自的優缺點在前序周遊的介紹中已提過了。

3.1 遞歸算法

  遞歸寫法比較簡單，注意防止死循環，明确遞歸的三要素。

遞歸的三要素：

1. 遞歸的定義（遞歸函數的傳回值、參數要如何定義）
2. 遞歸的拆解（遞歸如何向下拆分）
3. 遞歸的出口（遞歸的結束條件）

  遞歸又有兩種形式，周遊和分治。

3.1.1 周遊法（Traverse）

思路

  周遊的整個過程可以看成是為了完成某項大任務，于是上司親自下基層處理各項小任務，所有工作都“親曆親為”，參與了所有工作最終完成了大任務。

周遊法的主要遞歸函數一般不帶傳回值，會擁有​

​全局參數​

​或者貫穿整個遞歸過程的​

​函數參數​

​用來處理資料。

源碼

  C++版本：

/**
* @param root: A Tree
* @return: Postorder in ArrayList which contains node values.
*/
vector<int> postorderTraversal(TreeNode * root) {
    // write your code here
    vector<int> result;
    traverse(root, result);
    return result;
}

// 周遊法的遞歸函數，沒有傳回值，函數參數result貫穿整個遞歸過程用來記錄周遊的結果
void traverse(TreeNode * root, vector<int> & result) // 遞歸三要素之定義
{
    if (root == nullptr)
    {
        return; // 遞歸三要素之出口
    }

    // 前、中、後序三種周遊在此處對子樹與根節點的處理順序不同，後續周遊先處理左子樹，再處理右子樹，最後處理根節點
    traverse(root->left, result); // 遞歸三要素之拆解
    traverse(root->right, result);
    result.push_back(root->val);
}
      

3.1.2 分治法（Devide And Conquer）

  分治法的整個過程可以看成是為了完成某項大人物，于是上司把各項工作分派給各個下屬，各個下屬又把工作繼續細分層層向下分派給基層人員，每一級都隻需要擷取下級完成的任務結果即可，最終所有層級任務都完成了，大任務也對應完成了。

分治法的主要遞歸函數一般需要有傳回值，用來向上一層提供結果。

/**
* @param root: A Tree
* @return: Postorder in ArrayList which contains node values.
*/
// 由于主函數的形式已經符合分治法需要的形式（具有合适的傳回值），直接使用主函數做為遞歸函數
vector<int> postorderTraversal(TreeNode * root) {
    // write your code here
    vector<int> result;
    if (root == nullptr)
    {
        return result; // 遞歸三要素之出口
    }

    // 擷取左子樹的周遊結果
    vector<int> leftResult = postorderTraversal(root->left); // 遞歸三要素之拆解
    // 擷取右子樹的周遊結果
    vector<int> rightResult = postorderTraversal(root->right);

    // 前、中、後序三種周遊在此處對子樹與根節點的處理順序不同，後續周遊先處理左子樹，再處理右子樹，最後處理根節點
    result.insert(result.end(), leftResult.begin(), leftResult.end());
    result.insert(result.end(), rightResult.begin(), rightResult.end());
    result.push_back(root->val);

    return result;
}
      

3.2 非遞歸算法

3.2.1 二叉樹周遊的非遞歸通用解法

  在後序周遊的非遞歸算法中，采用針對二叉樹的前、中、後序周遊都比較通用的形式來解決周遊問題，在該通用解法中，後序周遊與​​前序周遊​​​​[1:1]​​、​​中序周遊​​​​[2:1]​​的不同之處在于對節點的解析操作發生的時刻與處理方式，前序周遊是“邊入棧邊解析”，中序周遊是“出棧時解析”，後序周遊則是“出棧時判斷條件解析”。

1. 左穿入棧到底；
2. 從棧内彈出目前節點，可能是​

   ​左子樹​

   ​或者​

   ​根節點​

   ​（相對），出棧時判斷解析；（前序周遊是在入棧時解析，中序是彈出時解析，後序是彈出時判斷條件解析）

判斷條件為：下一步是否需要解析右子樹？

需要解析右子樹：右子樹非空且未被解析；(cur->right != nullptr && prev != cur->right)

不需要解析右子樹：右子樹為空或已經被解析過。

1. ​

   ​右子樹​

   ​的根節點入棧，重複1、2步驟（即對右子樹做中序周遊），直到滿足循環結束條件，該二叉樹的後序周遊即在結果序列中。

後序周遊的初始條件和循環結束條件在通用解法中與前、中序周遊一緻。

初始條件：​

​棧為空​

​、​

​目前指針指向根節點​

​。

循環結束條件：​

​棧為空​

​且​

​目前指針為空​

後序周遊為了判斷右子樹是否已經被解析過，需要額外使用一個指針​

​prev​

​來記錄上一個解析過的節點。

/**
* @param root: A Tree
* @return: Postorder in ArrayList which contains node values.
*/
vector<int> postorderTraversal(TreeNode * root) {
    // write your code here
    vector<int> result;
    if (root == nullptr)
    {
        return result;
    }

    stack<TreeNode *> nodeStack;
    TreeNode * prev = nullptr; // prev用來記錄上一個解析過的節點
    TreeNode * cur = root;
    while (cur != nullptr || !nodeStack.empty())
    {
        while (cur != nullptr)
        {
            nodeStack.push(cur);
            cur = cur->left;
        }

        cur = nodeStack.top();
        // 此處是後序周遊不同的地方，出棧時判斷條件解析
        if (cur->right != nullptr && prev != cur->right) // 右子樹存在且未被解析
        {
            cur = cur->right; // 右節點成為下一個要處理的節點
        }
        else // 右子樹為空或者右子樹已經被解析過了
        {
            result.push_back(cur->val);
            nodeStack.pop();
            // 後序周遊在此處比前、中序周遊多了兩行
            prev = cur; // 使用prev記錄解析過的節點
            cur = nullptr; // 将cur至空，防止重複解析存在右子樹的節點
        }
    }

    return result;
}
      

圖解

  在邏輯上，前、中、後序周遊的過程大緻相同，可以參考​​前序周遊​​​​[1:2]​​的圖解，差別隻是解析操作發生的時刻和處理方式不同。

3.3 時間複雜度

  對二叉樹的周遊，不管使用什麼方式都是将整棵樹中的所有節點走一遍，是以算法的時間複雜度都為O(n)。

  關于二叉樹和分治法的時間複雜度的更多内容，在​​前序周遊​​​​[1:3]​​中已經進行了計算分析。

3.4 空間複雜度

  算法的空間複雜度，分治法為O(n)，上述其餘方法都為O(1)。

1. 二叉樹的前序周遊：javascript:void(0) ↩︎ ↩︎ ↩︎ ↩︎
2. 二叉樹的中序周遊：javascript:void(0) ↩︎ ↩︎