1 題目

??二叉樹的中序遍歷（Binary Tree Inorder Traversal）

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

2 描述

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

名詞：

遍歷

按照一定的順序?qū)渲兴泄?jié)點(diǎn)進(jìn)行訪問的過程叫做樹的遍歷。

中序遍歷

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

序列化規(guī)則：

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

樣例1：

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

     1
    / \
   2   3

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

樣例2：

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

        1
      /   \
    #       2
           /
          3

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

3 解決方案

??中序遍歷與前序遍歷^[1]一樣可以使用遞歸和非遞歸兩類方式，遞歸和非遞歸各自的優(yōu)缺點(diǎn)在前序遍歷中也提到了。

3.1 遞歸算法

??遞歸寫法比較簡單，主要注意防止死循環(huán)，遞歸的過程中要明確遞歸的三要素。

遞歸的三要素：

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

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

3.1.1 遍歷法（Traverse）

思路

??遍歷的整個過程可以看成是為了完成某項(xiàng)大任務(wù)，于是領(lǐng)導(dǎo)親自下基層處理各項(xiàng)小任務(wù)，所有工作都“親歷親為”，參與了所有工作最終完成了大任務(wù)。

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

源碼

??C++版本：

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

    return result;
}

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

    // 此處與前序遍歷不同，先處理左子樹，再處理根節(jié)點(diǎn)，最后處理右子樹
    traverse(cur->left, result); // 遞歸三要素之拆解
    result.push_back(cur->val);
    traverse(cur->right, result);
}

3.1.2 分治法（Devide And Conquer）

思路

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

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

源碼

??C++版本：

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

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

    // 此處與前序遍歷不同，先處理左子樹，再處理根節(jié)點(diǎn)，最后處理右子樹
    result.insert(result.end(), leftResult.begin(), leftResult.end());
    result.push_back(root->val);
    result.insert(result.end(), rightResult.begin(), rightResult.end());

    return result;
}

3.2 非遞歸算法

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

思路

??在中序遍歷的非遞歸算法中，與前序遍歷^[1:1]唯一的不同之處在于對節(jié)點(diǎn)的解析操作發(fā)生的時刻，前序遍歷是“邊入棧邊解析”，而中序遍歷是“出棧時解析”。

1. 左穿入棧到底；
2. 從棧內(nèi)彈出當(dāng)前節(jié)點(diǎn)，可能是左子樹或者根節(jié)點(diǎn)（相對），出棧時解析；
3. 右子樹的根節(jié)點(diǎn)入棧，重復(fù)1、2步驟（即對右子樹做中序遍歷），直到滿足循環(huán)結(jié)束條件，該二叉樹的中序遍歷即在結(jié)果序列中。

中序遍歷的初始條件和循環(huán)結(jié)束條件在通用解法中與前序遍歷一致。
初始條件：棧為空、當(dāng)前指針指向根節(jié)點(diǎn)。
循環(huán)結(jié)束條件：棧為空且當(dāng)前指針為空。

源碼

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

    stack<TreeNode *> nodeStack;
    TreeNode * cur = root;
    while (!nodeStack.empty() || cur != nullptr)
    {
        while (cur != nullptr)
        {
            nodeStack.push(cur);
            cur = cur->left;
        }

        cur = nodeStack.top();
        result.push_back(cur->val); // 此處是通用解法中唯一與前序遍歷不同的地方，出棧時解析
        nodeStack.pop();
        cur = cur->right;
    }
}

圖解

??在邏輯上，中序遍歷的過程與前序遍歷^[1:2]基本一致，可以參考前序遍歷的圖解，區(qū)別只是解析操作發(fā)生的時刻不同。

3.3 時間復(fù)雜度

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

??關(guān)于二叉樹和分治法的時間復(fù)雜度的更多內(nèi)容，在前序遍歷^[1:3]中已經(jīng)進(jìn)行了計算分析。

3.4 空間復(fù)雜度

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