1 題目

??二叉樹的前序遍歷（Binary Tree Preorder Traversal）

lintcode：題號——66，難度——easy

2 描述

??給出一棵二叉樹，返回其節(jié)點值的前序遍歷。

名詞：

遍歷

按照一定的順序對樹中所有節(jié)點進行訪問的過程叫做樹的遍歷。

前序遍歷

在二叉樹中，首先訪問根結點然后遍歷左子樹，最后遍歷右子樹，在遍歷左右子樹時，仍然采用這種規(guī)則，這樣的遍歷方式叫做二叉樹的前序遍歷。

序列化規(guī)則：

使用大括號包裹節(jié)點序列來表示二叉樹，首個數據為根節(jié)點，后面接著是其左兒子和右兒子節(jié)點值，"#"表示不存在該子節(jié)點，之后以此類推。

樣例1：

輸入：二叉樹 = {1,2,3}
輸出：[1,2,3]
解釋：上述{1,2,3}序列按照序列化規(guī)則表示的二叉樹如下

     1
    / \
   2   3

按照前序遍歷規(guī)則，先根再左右子樹，順序即為[1,2,3]

樣例2：

輸入：二叉樹 = {1,#,2,3}
輸出：[1,2,3]
解釋：上述{1,#,2,3}序列按照序列化規(guī)則表示的二叉樹如下

        1
      /   \
    #       2
           /
          3

按照前序遍歷規(guī)則，先根再左右子樹，順序同樣為[1,2,3]

3 解決方案

??二叉樹的遍歷可以使用遞歸和非遞歸兩種方式：

• 使用遞歸的方式編寫能夠減少思維復雜度，但是在二叉樹深度很深的情況下，由于編程語言一般會限制遞歸調用的深度，遞歸層數太深會導致程序調用的棧溢出。
• 使用非遞歸的方式比較難于理解，雖然會使用到棧，但只是存儲數值，不會產生上述程序調用的棧溢出情況。

3.1 遞歸算法

??程序在執(zhí)行過程中調用自己，叫做遞歸。遞歸通?？梢园岩粋€大型復雜的問題層層轉化為一個與原問題相似的規(guī)模較小的問題來求解，遞歸策略只需少量的程序代碼就可描述出解題過程所需要的多次重復計算。

遞歸的三個要素（編程中）：

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

??遞歸又有兩種形式，遍歷和分治。

3.1.1 遍歷法（Traverse）

思路

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

遍歷法的主要遞歸函數一般不帶返回值，會擁有全局參數或者貫穿整個遞歸過程的函數參數用來處理數據。

源碼

??C++版本：

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

    return result;
}

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

    result.push_back(curNode->val);
    traversa(curNode->left, result); // 遞歸三要素之拆解，
    traversa(curNode->right, result);
}

3.1.2 分治法（Devide And Conquer）

思路

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

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

源碼

??C++版本：

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

    // 獲取左子樹的遍歷結果
    vector<int> leftResult = preorderTraversal(root->left); // 遞歸三要素之拆解
    // 獲取右子樹的遍歷結果
    vector<int> rightResult = preorderTraversal(root->right);

    // 組合左右子樹的返回值
    result.push_back(root->val);
    result.insert(result.end(), leftResult.begin(), leftResult.end());
    result.insert(result.end(), rightResult.begin(), rightResult.end());

    return result;
}

3.2 非遞歸算法

3.2.1 二叉樹遍歷的非遞歸通用解法

思路

??在非遞歸算法中，需要用到數據結構“?！眮肀４娑鏄浔闅v過程中的狀態(tài)，模擬整個前序遍歷的路徑。下面提供一種針對二叉樹的前、中、后序遍歷都比較通用的形式來解決遍歷問題。

1. 左穿入棧到底，邊入棧邊解析；（解析：即向結果序列插入節(jié)點值）
2. 從棧內彈出當前節(jié)點，可能是左子樹或者根節(jié)點（相對）；（節(jié)點在步驟1已解析完成）
3. 右子樹的根節(jié)點入棧，重復3、4、5步驟（即對右子樹做中序遍歷），直到滿足循環(huán)結束條件，該二叉樹的前序遍歷即在結果序列中。

初始條件：棧為空、當前指針指向根節(jié)點。
循環(huán)結束條件：棧為空且當前指針為空。

源碼

/**
* @param root: A Tree
* @return: Preorder in ArrayList which contains node values.
*/
vector<int> preorderTraversal(TreeNode * root) {
    // write your code here
    vector<int> result;
    if (root == nullptr)
    {
        return result;
    }
    
    stack<TreeNode *> nodeStack; // 空棧
    TreeNode * cur = root; // cur指針指向根節(jié)點
    while (!nodeStack.empty() || cur != nullptr) // 棧和cur指針都不為空，則繼續(xù)循環(huán)
    {
        while (cur != nullptr) // while循環(huán)完成左穿入棧的步驟
        {
            result.push_back(cur->val);
            nodeStack.push(cur);
            cur = cur->left;
        }
        
        cur = nodeStack.top();
        nodeStack.pop(); // 彈出節(jié)點（左子樹、根節(jié)點）
        cur = cur->right; // cur指向右支，目的是讓下一次循環(huán)時將右支入棧
    }
    
    return result;
}

圖解

??非遞歸的解法理解起來比較不容易一些，可以邊調試邊理解，邏輯比較繞。

主要規(guī)律就是“左穿入棧解析->彈出已解析的棧頂->壓入未解析的右子樹”不斷重復。

樣例：{1,2,3,4,5,6,7}

初始狀態(tài)：

         1
       /   \
      2     3
     / \   / \
    4   5 6   7

nodeStack——（棧底）空（棧頂）
cur——1
result——空

第一輪while循環(huán)：

圖形表示棧nodeStack的狀態(tài)
         1
       /
      2
     /
    4   左穿入棧到底，邊入棧邊解析

nodeStack——（棧底）1，2，4（棧頂）
cur——nullptr，cur此時指向4的左孩子
result——1，2，4（只在解析時才插入新值）

         1
       /
      2 彈出棧頂

nodeStack——（棧底）1，2（棧頂）
cur——nullptr，cur被指向之前的棧頂4，彈出棧頂之后，此時指向4的右孩子

第二輪while循環(huán)：

         1
       /
      2 循環(huán)開始時cur指向空，跳過左穿入棧的過程

nodeStack——（棧底）1，2（棧頂）
cur——nullptr，cur指向4的右孩子

         1  彈出棧頂

nodeStack——（棧底）1（棧頂）
cur——5，cur被指向之前的棧頂2，彈出棧頂之后，此時指向2的右孩子

第三輪while循環(huán)：

         1
       /
      空 節(jié)點2不在棧內
       \ 
        5   循環(huán)開始時cur指向5，左穿入棧到底，邊入棧邊解析

nodeStack——（棧底）1，5（棧頂）
cur——nullptr，cur指向5的左孩子
result——1，2，4，5

         1

nodeStack——（棧底）1（棧頂）
cur——nullptr，cur被指向之前的棧頂5，彈出棧頂之后，此時指向5的右孩子

第四輪while循環(huán)：

         1  循環(huán)開始時cur指向空，跳過左穿入棧的過程

nodeStack——（棧底）1（棧頂）
cur——nullptr，cur指向5的右孩子

         空 彈出棧頂

nodeStack——（棧底）空（棧頂）
cur——3，cur被指向之前的棧頂1，彈出棧頂之后，此時指向1的右孩子

第五輪while循環(huán)：

         空
           \
            3
           /
          6 左穿入棧，邊入棧邊解析

nodeStack——（棧底）3，6（棧頂）
cur——nullptr，cur指向6的左孩子
result——1，2，4，5，3，6

         空
           \
            3 彈出棧頂

nodeStack——（棧底）3（棧頂）
cur——nullptr，cur被指向之前的棧頂6，彈出棧頂之后，此時指向6的右孩子

第六輪while循環(huán)：

         空
           \
            3 循環(huán)開始時cur指向空，跳過左穿入棧的過程

nodeStack——（棧底）3（棧頂）
cur——nullptr，cur指向6的右孩子

         空  彈出棧頂

nodeStack——（棧底）空（棧頂）
cur——7，cur被指向之前的棧頂3，彈出棧頂之后，此時指向3的右孩子

第七輪while循環(huán)：

         空
           \
            空
             \
              7 左穿入棧，邊入棧邊解析

nodeStack——（棧底）7（棧頂）
cur——nullptr，cur指向7的左孩子
result——1，2，4，5，3，6，7

         空
           \
            空  彈出棧頂

nodeStack——（棧底）空（棧頂）
cur——nullptr，cur被指向之前的棧頂7，彈出棧頂之后，此時指向7的右孩子
result——1，2，4，5，3，6，7

此時，nodeStack和cur都為空，滿足循環(huán)結束條件，跳出循環(huán)。

此時的result序列即為該二叉樹的前序遍歷。

3.2.2 前序遍歷的非遞歸解法二

思路

??這個代碼和通用解法的不同點有兩個：

1. 初始條件：棧初始化包含根節(jié)點、當前指針指向根節(jié)點；
2. 循環(huán)結束條件：棧為空；

源碼

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

    stack<TreeNode *> nodeStack;
    nodeStack.push(root); // 初始化時候，根節(jié)點入棧
    TreeNode * cur = root;
    while (!nodeStack.empty()) // 循環(huán)只需要判斷棧是否為空
    {
        while (cur != nullptr)
        {
            result.push_back(cur->val);
            nodeStack.push(cur);
            cur = cur->left;
        }

        cur = nodeStack.top();
        nodeStack.pop();
        cur = cur->right;
    }
}

3.2.3 前序遍歷的非遞歸解法三

思路

??這個解法比前兩種非遞歸解法要容易理解，但為了統(tǒng)一前、中、后序的遍歷方式，建議記非遞歸的通用解法，按照前序遍歷的規(guī)則來處理節(jié)點。步驟如下：

1. 循環(huán)前向棧內壓入根節(jié)點；
2. 解析cur，彈出cur；
3. 右子樹入棧；
4. 左子樹入棧；
5. 重復2、3、4步驟，直到?？?。

初始條件：棧初始化包含根節(jié)點、當前指針指向空；
循環(huán)結束條件：棧為空；

源碼

/**
* @param root: A Tree
* @return: Preorder in ArrayList which contains node values.
*/
vector<int> preorderTraversal(TreeNode * root){
    // write your code here
    vector<int> result;
    if (root == nullptr)
    {
        return result;
    }
    
    stack<TreeNode *> nodeStack;
    nodeStack.push(root); // 循環(huán)前壓入根節(jié)點
    TreeNode * cur = nullptr;
    while (!nodeStack.empty())
    {
        cur = nodeStack.top();
        result.push_back(cur->val); // 解析棧頂節(jié)點
        nodeStack.pop(); // 彈出已解析的節(jié)點
        if (cur->right != nullptr)
        {
            nodeStack.push(cur->right); // 壓入右子樹
        }
        if (cur->left != nullptr)
        {
            nodeStack.push(cur->left); // 壓入左子樹
        }
    }
    
    return result;
}

3.3 時間復雜度

??對二叉樹的遍歷，不管使用什么方式都是將整棵樹中的所有節(jié)點走一遍，所以算法的時間復雜度都為O(n)。

??關于二叉樹和分治法的時間復雜度，如果節(jié)點操作的的時間復雜度為O(1)，總復雜度為O(n)：

T(n) = 2 * T(n/2) + O(1)
     = 2 * (2*T(n/4) + O(1)) + O(1)
     = 4 * T(n/4) + 2 * O(1) + O(1)
     = 4 * (2*T(n/8) + O(1)) + O(1)
     = 8 * T(n/8) + 4 * O(1) + 2 * O(1) + O(1)
     = n * T(n/n) + O(n/2 + n/4 + …… + 1)
     = O(n) + O(n)
     = O(n)

??如果節(jié)點操作的的時間復雜度為O(n)，總復雜度為O(nlogn)：

T(n) = 2 * T(n/2) + O(n)
     = 2 * (2*T(n/4) + O(n/2)) + O(n)
     = 4 * T(n/4) + 2*O(n/2) + O(n)
     = 4 * (2*T(n/8) + O(n/4)) + 2*O(n/2) + O(n)
     = 8 * T(n/8) + 4*O(n/4) + 2*O(n/2) + O(n)
     = n * T(n/n) + O(n) + O(n) + …… + O(n)
     = O(n) + logn*O(n)
     = O(nlogn)

3.4 空間復雜度

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

4 總結

??二叉樹的遍歷在一般使用遞歸算法，在二叉樹較大的情況下才使用非遞歸的算法。