專項(xiàng)練習(xí)
任何數(shù)據(jù)結(jié)構(gòu)與算法技巧的熟悉都需要我們一定題目量的訓(xùn)練馒吴。訓(xùn)練最終達(dá)到的目的是下意識(shí)的把我們見(jiàn)到的陌生的題目轉(zhuǎn)換為我們做過(guò)的題目類型。
我希望小伙伴們刻意的按照下面的步驟去思考：
（1）分析提取題目特征
（2）遍歷數(shù)據(jù)結(jié)構(gòu)世吨，先判斷哪幾種數(shù)據(jù)結(jié)構(gòu)與題目描述符合
（3）遍歷算法思想與技巧，看看原題目是否可以通過(guò)轉(zhuǎn)換變?yōu)槲覀兪煜さ念}目呻征。
二叉樹(shù)
二叉樹(shù)的非遞歸遍歷（先根序耘婚、中根序、后根序）
深度優(yōu)先遍歷的非遞歸實(shí)現(xiàn)一般都會(huì)借助棧怕犁，先根序與中根序的實(shí)現(xiàn)模式比較接近边篮，后根序稍微復(fù)雜一些。
144. Binary Tree Preorder Traversal 先根序遍歷
使用到的輔助數(shù)據(jù)結(jié)構(gòu)：vector奏甫、stack
使用到的算法思想：深度優(yōu)先遍歷的非遞歸
//先根序遍歷
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> result;
stack<TreeNode*> p;
while(root || !p.empty())
{
//從根節(jié)點(diǎn)開(kāi)始遇到左子樹(shù)就開(kāi)始入棧戈轿，一直到葉子節(jié)點(diǎn)
while(root)
{
p.push(root);
result.push_back(root->val);
root = root->left;
}
//彈出當(dāng)前結(jié)點(diǎn)
root = p.top();
p.pop();
//開(kāi)始遍歷右子樹(shù)
root = root->right;
}
return result;
}
};
還是以左子樹(shù)的遍歷為例，流程入下：
（1）左子樹(shù)一直入棧阵子，直到葉子結(jié)點(diǎn)
（2）4出棧
（3）4沒(méi)有右子樹(shù)思杯，2繼續(xù)出棧，2有右子樹(shù)5挠进，5沒(méi)有左子樹(shù)
（4）1出棧
94. Binary Tree Inorder Traversal 中根序遍歷
中根序遍歷使用到的數(shù)據(jù)結(jié)構(gòu)與算法思想與先根序一致色乾，所不同是root-value的放入時(shí)機(jī)
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> result;
stack<TreeNode*> p;
while(root || !p.empty())
{
//從根節(jié)點(diǎn)開(kāi)始遇到左子樹(shù)就開(kāi)始入棧，一直到葉子節(jié)點(diǎn)
while(root)
{
p.push(root);
root = root->left;
}
//彈出當(dāng)前結(jié)點(diǎn)
root = p.top();
p.pop();
result.push_back(root->val);
//開(kāi)始遍歷右子樹(shù)
root = root->right;
}
return result;
}
};
145. Binary Tree Postorder Traversal 后根序遍歷
后根序使用的數(shù)據(jù)結(jié)構(gòu)與算法仍舊與前序领突、中序相同暖璧，但程序結(jié)構(gòu)略有不同，原因是后根序需要在遍歷完左君旦、右子樹(shù)后再訪問(wèn)一次根結(jié)點(diǎn)澎办。所以需要額外保留一個(gè)指針變量記錄上次訪問(wèn)的結(jié)點(diǎn)。
先看代碼
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> result;
stack<TreeNode*> p;
TreeNode* root1 = root;
TreeNode* preNode = nullptr;
do
{
//同樣從根結(jié)點(diǎn)開(kāi)始一直把左子樹(shù)入棧金砍，直到葉子結(jié)點(diǎn)
while(root1)
{
p.push(root1);
root1 = root1->left;
}
//使用preNode 保留上次訪問(wèn)的結(jié)點(diǎn)局蚀，用來(lái)判斷當(dāng)前root結(jié)點(diǎn)是否是訪問(wèn)完右結(jié)點(diǎn)的root結(jié)點(diǎn)
preNode = nullptr;
while(!p.empty())
{
root1 = p.top();
p.pop();
//如果已經(jīng)訪問(wèn)完了右結(jié)點(diǎn)，則當(dāng)前root結(jié)點(diǎn)可以放入result中
if(root1->right == preNode)
{
result.push_back(root1->val);
preNode = root1;
}
//如果root結(jié)點(diǎn)沒(méi)有右結(jié)點(diǎn)或者還沒(méi)訪問(wèn)過(guò)右結(jié)點(diǎn)恕稠，則繼續(xù)入棧
else{
p.push(root1);
root1 = root1->right;
break;
}
}
}while(!p.empty());
return result;
}
};
以下面二叉樹(shù)中的245結(jié)點(diǎn)為例說(shuō)明上面程序流程琅绅，我們已經(jīng)以1為根結(jié)點(diǎn)已經(jīng)遍歷到了最左邊的葉子結(jié)點(diǎn)4
102. Binary Tree Level Order Traversal 二叉樹(shù)的層序遍歷
使用到的輔助數(shù)據(jù)結(jié)構(gòu)：vector、queue
使用到的算法思想：廣度優(yōu)先遍歷的非遞歸和遞歸
//遞歸
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int> > res;
levelorder(root,0,res);
return res;
}
void levelorder(TreeNode* root, int level, vector<vector<int> >& res)
{
if(!root)
return;
if(res.size() == level)
res.push_back({});
res[level].push_back(root->val);
if(root->left)
levelorder(root->left,level+1,res);
if(root->right)
levelorder(root->right,level+1,res);
}
};
//非遞歸
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int> >res;
if(root == NULL)
return res;
queue<TreeNode*> q;
q.push(root);
while(!q.empty())
{
vector<int> oneLevel;
int size = q.size();
for(int i = 0; i <size; ++i)
{
TreeNode *node = q.front();
q.pop();
oneLevel.push_back(node->val);
if(node->left)
q.push(node->left);
if(node->right)
q.push(node->right);
}
res.push_back(oneLevel);
}
return res;
}
};
怎樣應(yīng)對(duì)IT面試與筆試-（一）
怎樣應(yīng)對(duì)IT面試與筆試-（二）
怎樣應(yīng)對(duì)IT面試與筆試-（三）
怎樣應(yīng)對(duì)IT面試與筆試-（四）
怎樣應(yīng)對(duì)IT面試與筆試-（五）
怎樣應(yīng)對(duì)IT面試與筆試-（五-1）
怎樣應(yīng)對(duì)IT面試與筆試-（六）
怎樣應(yīng)對(duì)IT面試與筆試-（七）
怎樣應(yīng)對(duì)IT面試與筆試-（八）
怎樣應(yīng)對(duì)IT面試與筆試-（九）
怎樣應(yīng)對(duì)IT面試與筆試-（十）
怎樣應(yīng)對(duì)IT面試與筆試-（十一）
怎樣應(yīng)對(duì)IT面試與筆試-（十二）
怎樣應(yīng)對(duì)IT面試與筆試-（十三）
怎樣應(yīng)對(duì)IT面試與筆試-（十四）
怎樣應(yīng)對(duì)IT面試與筆試-（十五）
怎樣應(yīng)對(duì)IT面試與筆試-（十六）
