15 二叉樹的后序遍歷（Binary Tree Postorder Traversal）
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 遞歸算法
??遞歸寫法比較簡單，注意防止死循環，明確遞歸的三要素。
遞歸的三要素：
- 遞歸的定義（遞歸函數的返回值、參數要如何定義）
- 遞歸的拆解（遞歸如何向下拆分）
- 遞歸的出口（遞歸的結束條件）
??遞歸又有兩種形式，遍歷和分治。
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）
思路
??分治法的整個過程可以看成是為了完成某項大人物，于是領導把各項工作分派給各個下屬，各個下屬又把工作繼續細分層層向下分派給基層人員，每一級都只需要獲取下級完成的任務結果即可，最終所有層級任務都完成了，大任務也對應完成了。
分治法的主要遞歸函數一般需要有返回值，用來向上一層提供結果。
源碼
??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;
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]的不同之處在于對節點的解析操作發生的時刻與處理方式，前序遍歷是“邊入棧邊解析”，中序遍歷是“出棧時解析”，后序遍歷則是“出棧時判斷條件解析”。
- 左穿入棧到底；
- 從棧內彈出當前節點，可能是
左子樹或者根節點（相對），出棧時判斷解析；（前序遍歷是在入棧時解析，中序是彈出時解析，后序是彈出時判斷條件解析）
判斷條件為：下一步是否需要解析右子樹？
需要解析右子樹：右子樹非空且未被解析；(cur->right != nullptr && prev != cur->right)
不需要解析右子樹：右子樹為空或已經被解析過。
右子樹的根節點入棧，重復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)。
浙公網安備 33010602011771號