九十五、二叉樹的遞歸和非遞歸的遍歷算法模板
「@Author：Runsen」
刷Leetcode，需要知道一定的算法模板，本次先總結(jié)下二叉樹的遞歸和非遞歸的遍歷算法模板。
二叉樹的四種遍歷方式，前中后加上層序遍歷。對于二叉樹的前中后層序遍歷，每種遍歷都可以遞歸和循環(huán)兩種實(shí)現(xiàn)方法，且每種遍歷的遞歸實(shí)現(xiàn)都比循環(huán)實(shí)現(xiàn)要簡潔。下面做一個小結(jié)，看了《代碼隨想錄》哈工大大佬的刷題指南，深受啟發(fā)，因，下面代碼有一定來源《代碼隨想錄》。
遞歸
下面?zhèn)未a是二叉樹遍歷的遞歸算法模板，順序是中左右，也就是前序遍歷，改變中左右三行代碼的順序，前中后序三種遞歸遍歷輕松解決。
def preorderTraversal(root: TreeNode) -> List[int]:
res = []
def help(root):
if not root: return
res.append(root.val) # 中
help(root.left) # 左
help(root.right) # 右
help(root)
return res
對此也提供C++代碼，遞歸算法模板一定要加上終止條件，不然一入遞歸深似海，從此offer是路人，來源代碼隨想錄。
void help(TreeNode * root , vector<int> &res) {
if (root == nullptr) {
return;
}
res.push_back(root->val); // 中
help(root->left,res); // 左
help(root->right,res); //右
}
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
help(root,res);
return res;
}
迭代
迭代遍歷二叉樹的比遞歸難度加大，其實(shí)使用了一個棧的數(shù)據(jù)結(jié)構(gòu)，《代碼隨想錄》非常巧妙的使用空指針來作標(biāo)記，原理是將處理的節(jié)點(diǎn)放入棧之后，緊接著放入一個空指針作為標(biāo)記。
由于棧是先進(jìn)后出，所以前序遍歷的順序中左右，在加到棧中，需要反過來進(jìn)行添加，每添加一個元素在后面添加一個空指針，在Python中也可以使用None來代替。
下面是具體的偽代碼，至于中序和后序遍歷，改下向棧中添加節(jié)點(diǎn)的順序即可。
def preorderTraversal(root: TreeNode) -> List[int]:
result = []
st= []
# 1、判斷root
if root:
st.append(root)
while st:
node = st.pop()
if node != None:
# 右左中 添加到棧中，然后中左右拿出
if node.right: #右
st.append(node.right)
if node.left: #左
st.append(node.left)
st.append(node) #中
# 添加一個空指針 記錄節(jié)點(diǎn)
st.append(None)
else:
# node是空指針，那么下一個就是加入的節(jié)點(diǎn)
node = st.pop()
result.append(node.val)
return result
下面是具體的C++代碼，由于C++中的stack中pop之后，沒有返回值，因此需要額外注意。
vector<int> preorderTraversal(TreeNode* root) {
vector<int>res;
stack<TreeNode*> st;
if (root != nullptr) st.push(root);
while(!st.empty()){
TreeNode* node = st.top();
if(node != nullptr){
st.pop();
if(node->right) st.push(node->right);
if (node->left) st.push(node->left);
st.push(node);
st.push(NULL);
}else{
// 需要額外注意下
st.pop();
node = st.top();
st.pop();
res.push_back(node->val);
}
}
return res;
}
層次遍歷
其實(shí)，樹的遍歷也分為兩種，分別是深度優(yōu)先遍歷和廣度優(yōu)先遍歷。關(guān)于樹的不同深度優(yōu)先遍歷（前序，中序和后序遍歷）就是遞歸和非遞歸的寫法。廣度優(yōu)先遍歷在樹中，就是層次遍歷。
在二叉樹的層級遍歷中，我們需要用到隊(duì)列這個數(shù)據(jù)結(jié)構(gòu)，幫助我們完成遍歷。
在Python偽代碼中，
def levelOrder(root: TreeNode) -> List[List[int]]:
# 1、判斷root
if not root:
return []
# 把root添加到quene 中
quene = [root]
out_list = []
while quene:
# while 第一步就是求length
length = len(queue)
in_list = []
for _ in range(length):
# 在C++中，這里需要兩行
curnode = queue.pop(0) # （默認(rèn)移除列表最后一個元素）這里需要移除隊(duì)列最頭上的那個
in_list.append(curnode.val)
if curnode.left: queue.append(curnode.left)
if curnode.right: queue.append(curnode.right)
out_list.append(in_list)
return out_list
通過上面的Python偽代碼，進(jìn)行書寫更高效的C++代碼。
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> res;
queue<TreeNode*> que;
// 判斷 root
if (root != nullptr) que.push(root);
while(!que.empty()) {
// 開始先求隊(duì)列的長度
int size = que.size();
vector<int> vec;
// 迭代添加節(jié)點(diǎn)元素
for (int i = 0 ; i<size; i++){
TreeNode* node = que.front();
que.pop();
vec.push_back(node->val);
if (node->left) que.push(node->left);
if (node->right) que.push(node->right);
}
res.push_back(vec);
}
return res;
}
};
上述為樹的遍歷模板。其實(shí)本質(zhì)上也是深度優(yōu)先遍歷與廣度優(yōu)先遍歷的算法模板，許多其它操作都是建立在樹遍歷操作的基礎(chǔ)之上，因此掌握樹的所有遍歷方法，等于解決了一半樹的題目。