今日刷題重點–二叉樹的遞歸+疊代周遊
144. 二叉樹的前序周遊
給你二叉樹的根節點 root ，傳回它節點值的 前序 周遊。
示例 1：
輸入：root = [1,null,2,3]
輸出：[1,2,3] 示例 2：
輸入：root = []
輸出：[] 示例 3：
輸入：root = [1]
輸出：[1] 其他相似問題
145. 二叉樹的後序周遊
94. 二叉樹的中序周遊
1.遞歸
//遞歸的做法
class Solution {
public:
void traverse(TreeNode* cur,vector<int>& vec) { //遞歸周遊
if(cur) { //先序周遊
vec.push_back(cur->val);
traverse(cur->left,vec);
traverse(cur->right,vec);
}
}
vector<int> preorderTraversal(TreeNode* root) {
vector<int> vec;
traverse(root,vec);
return vec;
};
}; 2.疊代
先序周遊
因為遞歸底層使用的是棧,是以我們可以直接使用棧來解決問題.
先序是按照中左右的順序,每次先處理的是中間節點,那麼我們處理時要先将右孩子加入棧,再加入左孩子.
為什麼要按照這樣的入棧順序呢?因為先入棧的後周遊,後入棧的先周遊.
如圖所示:
參考代碼:
//先序周遊 中左右
vector<int> preorderTraversal(TreeNode* root) {
stack<TreeNode*> tab;
vector<int> res;
if(root==NULL) {
return res;
}
tab.push(root);
while(!tab.empty()) {
TreeNode* cur = tab.top();
tab.pop();
res.push_back(cur->val);
if(cur->right) {
tab.push(cur->right);
}
if(cur->left) {
tab.push(cur->left);
}
}
return res;
}; 後序周遊
由于先序是:中左右,後序是:左右中,是以我們可以調整下先序代碼的順序便可完成操作.
//後序周遊: 左右中 可以直接從前序的代碼上修改一點即可.
vector<int> postorderTraversal(TreeNode* root) {
stack<TreeNode*> tab;
vector<int> res;
if(root==NULL) {
return res;
}
tab.push(root);
while(!tab.empty()) {
TreeNode* cur = tab.top();
tab.pop();
res.push_back(cur->val);
if(cur->left) {
tab.push(cur->left);
}
if(cur->right) {
tab.push(cur->right);
}
}
reverse(res.begin(),res.end());
return res;
} 中序周遊
那麼再看看中序周遊，中序周遊是左中右，先通路的是二叉樹頂部的節點，然後一層一層向下通路，直到到達樹左面的最底部，再開始處理節點（也就是在把節點的數值放進result數組中），這就造成了處理順序和通路順序是不一緻的。
//中序周遊
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> tab;
TreeNode* cur = root;
if(root==NULL){
return res;
}
while(cur!=NULL || !tab.empty()){//直到棧為空并且目前節點 也為空,則結束.
if(cur!=NULL){
tab.push(cur);//如果目前節點不為空,則将目前節點先壓入棧,繼續進行通路.
cur = cur->left;//當把目前結點的左子樹通路完了,在處理當期節點. =>左
}else{//結點的左子樹為空,則開始彈出該節點處理完畢後,開始通路處理右子樹.
cur = tab.top();//
tab.pop();
res.push_back(cur->val);//中
cur = cur->right; //右
}
}
return res;
}