【Warrior刷題筆記】劍指offer 32. 三道題，讓你學會二叉樹的深度廣度優先遍歷與遞歸迭代技術
題目一 劍指 Offer 32 – I. 從上到下列印二叉樹
來源：力扣（LeetCode）
鏈接：//leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-lcof/
1.描述
從上到下列印出二叉樹的每個節點，同一層的節點按照從左到右的順序列印。
2.示例
- 示例 1：
給定二叉樹: [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回：
[3,9,20,15,7]
解法一 廣度優先遍歷+輔助隊列
解題思路
看到題不難想到最簡單的辦法就是藉助一個隊列，對二叉樹進行廣度優先遍歷。
1.如果根節點為空，直接返回空數組，否則入隊根節點；
2.將隊頭節點值加入答案數組；
3.入隊隊頭節點的非空子節點，將隊頭節點出隊。
4.重複2,3過程直到隊列為空。
程式碼
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> levelOrder(TreeNode* root) {
vector<int> ans;//存儲答案
if(!root) return ans;//如果根節點為空，返回空答案數組
queue<TreeNode*> q;//輔助隊列
q.push(root);//根節點入隊
while(!q.empty()){//只要隊列不為空
ans.push_back(q.front()->val);//將隊頭節點值加入答案數組
//入隊隊頭節點的非空子節點
if(q.front()->left) q.push(q.front()->left);
if(q.front()->right) q.push(q.front()->right);
q.pop();//將隊頭節點出隊
}
return ans;//返回答案
}
};
複雜度分析
時間複雜度： O(m)。m二叉樹節點數，遍歷整棵二叉樹需要O(m)時間。
空間複雜度： O(m)。存儲答案和使用輔助隊列的空間消耗。
解法二 深度優先搜索+輔助數組
解題思路
除了解法一較為直觀的廣度優先搜索外，我們也可以使用深度優先搜索+輔助二維數組解決本題。
具體的，我們對二叉樹進行深度優先搜索，同時維護一個層數level，初始時level為0。每進入一層遞歸，也即從當前節點遍歷孩子節點時，層數就加一，然後通過層數作為下標訪問二維數組將節點值加入對應層的一維數組，最後再將二維數組按層捋直即為最終答案。
程式碼
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> levelOrder(TreeNode* root) {
vector<int> ans;//存儲答案
if(!root) return ans;//如果根節點為空，返回空數組
vector<vector<int>> aid;//輔助數組
dfs(root, 0, aid);//深度優先遍歷
for(auto a : aid) ans.insert(ans.end(), a.begin(), a.end());//將二維數組按層捋直
return ans; //返回答案
}
void dfs(TreeNode* root, int level, vector<vector<int>>& aid){
if(!root) return;//如果節點為空，返回
if(aid.size()<=level){//如果該層數組還未創建，創建之
vector<int> temp;
aid.push_back(temp);
}
aid[level].push_back(root->val);//將節點值加入對應層數組
dfs(root->left, level+1, aid);//遍歷左子節點，同時level+1
dfs(root->right, level+1, aid);//遍歷右子節點，同時level+1
}
};
複雜度分析
時間複雜度： O(m)。遞歸以及把二維數組捋直的時間消耗
空間複雜度： O(m)。遞歸以及輔助數組、答案數組的空間消耗。
題目二 劍指 Offer 32 – II. 從上到下列印二叉樹 II
來源：力扣（LeetCode）
鏈接：//leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-ii-lcof/
1.描述
從上到下按層列印二叉樹，同一層的節點按從左到右的順序列印，每一層列印到一行。
2.示例
- 示例 1：
給定二叉樹: [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回其層次遍歷結果：
[
[3],
[9,20],
[15,7]
]
解法一 廣度優先搜索+輔助隊列
解題思路
參考題目一，我們可以寫出廣度優先搜索+輔助隊列的版本。
不過略有不同的是，我們需要選擇合適的方式進行分層。這裡使用兩個額外變數count和size進行分層操作，對每一層，size為層大小，初始時為1，即只有根節點的時候隊列的大小。每記錄一個節點，count值加一，當count等於size時，表示當前層已遍歷完畢，則更新層大小，重置count為0。
1.如果根節點為空，直接返回空數組，否則入隊根節點；
2.將隊頭節點值加入答案數組；
3.入隊隊頭節點的非空子節點，將隊頭節點出隊；
4.將count加一，若count等於size，則更新size，並重置count為0；
5.重複2,3，4過程直到隊列為空。
程式碼
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> ans;//存儲答案
if(!root) return ans;//如果根節點為空，返回空數組
queue<TreeNode*> q;//輔助隊列
q.push(root);//入隊根節點
int size = q.size(), count = 0;//初始化size和count
vector<int> temp;//輔助數組
while(!q.empty()){//只要隊列不為空
temp.push_back(q.front()->val);//記錄隊頭節點值
//入隊隊頭節點的非空子節點
if(q.front()->left) q.push(q.front()->left);
if(q.front()->right) q.push(q.front()->right);
q.pop();//出隊隊頭節點
++count;//將count+1
if(count == size){//若count==size，表示當前層已記錄完畢
ans.push_back(temp);//將temp加入答案數組
temp.clear();//清空temp
count = 0;//重置count為0
size = q.size();//更新size
}
}
return ans;//返回答案
}
};
複雜度分析
時間複雜度： O(m)。m為二叉樹節點數，遍歷整棵二叉樹需要O(m)時間。
空間複雜度： O(m)。輔助隊列，答案數組，輔助數組的空間消耗。
解法二 深度優先搜索+輔助數組
解題思路
除了解法一較為直觀的廣度優先搜索外，我們也可以使用深度優先搜索+輔助二維數組解決本題。
具體的，我們對二叉樹進行深度優先搜索，同時維護一個層數level，初始時level為0。每進入一層遞歸，也即從當前節點遍歷孩子節點時，層數就加一，然後通過層數作為下標訪問二維數組將節點值加入對應層的一維數組，遍歷完成後即為最終答案。
程式碼
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> ans;//存儲答案
if(!root) return ans;//如果根節點為空，返回空數組
dfs(root, 0, ans);//深度優先遍歷
return ans;//返回答案
}
void dfs(TreeNode* root, int level, vector<vector<int>>& aid){//深度優先遍歷
if(!root) return;//如果節點為空，直接返回
if(aid.size()<=level){//如果當前層數組還未創建，創建之
vector<int> temp;
aid.push_back(temp);
}
aid[level].push_back(root->val);//存入當前節點值到對應層
dfs(root->left, level+1, aid);//遍歷左孩子，層數加一
dfs(root->right, level+1, aid);//遍歷右孩子，層數加一
}
};
複雜度分析
時間複雜度： O(m)。遍歷二叉樹的時間消耗。
空間複雜度： O(m)。存儲答案和遞歸的棧空間消耗。
題目三 劍指 Offer 32 – III. 從上到下列印二叉樹 III
來源：力扣（LeetCode）
鏈接：//leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof/
1.描述
請實現一個函數按照之字形順序列印二叉樹，即第一行按照從左到右的順序列印，第二層按照從右到左的順序列印，第三行再按照從左到右的順序列印，其他行以此類推。
2.示例
- 示例 1：
給定二叉樹: [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回其層次遍歷結果：
[
[3],
[20,9],
[15,7]
]
解法一 廣度優先搜索+輔助隊列
解題思路
參考題目二，我們可以寫出廣度優先搜索+輔助隊列的版本。
我們需要選擇合適的方式進行分層。這裡使用兩個額外變數count和size進行分層操作，對每一層，size為層大小，初始時為1，即只有根節點的時候隊列的大小。每記錄一個節點，count值加一，當count等於size時，表示當前層已遍歷完畢，則更新層大小，重置count為0。不過略有不同的是，我們需要在遍歷完畢後對結果數組進行處理，也即翻轉偶數層數組。處理完畢後即為答案。
1.如果根節點為空，直接返回空數組，否則入隊根節點；
2.將隊頭節點值加入答案數組；
3.入隊隊頭節點的非空子節點，將隊頭節點出隊；
4.將count加一，若count等於size，則更新size，並重置count為0；
5.重複2,3，4過程直到隊列為空；
6.翻轉偶數層結果數組。
程式碼
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> ans;//存儲答案
if(!root) return ans;//如果根節點為空，返回空數組
queue<TreeNode*> q;//輔助隊列
q.push(root);//入隊根節點
int size = q.size(), count = 0;//初始化size和count
vector<int> temp;//輔助數組
while(!q.empty()){//只要隊列不為空
temp.push_back(q.front()->val);//記錄隊頭節點值
//入隊隊頭節點的非空子節點
if(q.front()->left) q.push(q.front()->left);
if(q.front()->right) q.push(q.front()->right);
q.pop();//出隊隊頭節點
++count;//將count+1
if(count == size){//若count==size，表示當前層已記錄完畢
ans.push_back(temp);//將temp加入答案數組
temp.clear();//清空temp
count = 0;//重置count為0
size = q.size();//更新size
}
}
for(int i = 0; i < m; ++i) if(i%2!=0) reverse(ans[i].begin(), ans[i].end());//翻轉偶數層
return ans;//返回答案
}
};
複雜度分析
時間複雜度： O(m)。m為二叉樹節點數，遍歷整棵二叉樹和翻轉偶數層需要O(m)時間。
空間複雜度： O(m)。輔助隊列，答案數組，輔助數組的空間消耗。
解法二 深度優先遍歷+輔助數組
解題思路
這裡也提供深度優先遍歷的版本。
程式碼
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> ans;//存儲答案
if(!root) return ans;//如果根節點為空，返回空數組
dfs(root, 0, ans);//深度優先遍歷
for(int i = 0; i < m; ++i) if(i%2!=0) reverse(ans[i].begin(), ans[i].end());//翻轉偶數層
return ans;//返回答案
}
void dfs(TreeNode* root, int level, vector<vector<int>>& aid){//深度優先遍歷
if(!root) return;//如果節點為空，直接返回
if(aid.size()<=level){//如果當前層數組還未創建，創建之
vector<int> temp;
aid.push_back(temp);
}
aid[level].push_back(root->val);//存入當前節點值到對應層
dfs(root->left, level+1, aid);//遍歷左孩子，層數加一
dfs(root->right, level+1, aid);//遍歷右孩子，層數加一
}
};
複雜度分析
時間複雜度： O(m)。遍歷二叉樹和翻轉偶數層的時間消耗。
空間複雜度： O(m)。存儲答案和遞歸的棧空間消耗。
一般說來，廣度優先遍歷更直觀，但是程式碼較長；而深度優先遍歷程式碼簡潔，但是較難理解。要多用多練，以掌握之。
更多知識內容分享：
部落格園個人主頁//home.cnblogs.com/u/newCoderTheWarrior
力扣個人主頁//leetcode-cn.com/profile/articles/
