Depth-first Search（深度優(yōu)先搜索）
104. Maximum Depth of Binary Tree
求二叉樹(shù)的最大深度問(wèn)題败京，經(jīng)典的深度優(yōu)先搜索
先給出代碼：
class Solution {
public:
int maxDepth(TreeNode* root) {
if (!root) return 0;
//先遞歸計(jì)算左邊子樹(shù)的最大深度
int l = 1+ maxDepth(root->left);
//再遞歸計(jì)算右邊子樹(shù)的最大深度
int r = 1+ maxDepth(root->right);
//返回兩者的最大值
return max(l,r);
}
};
為簡(jiǎn)單，我們僅以左子樹(shù)為例說(shuō)明毕泌，下面星星符號(hào)里的數(shù)字是函數(shù)的遞歸執(zhí)行順序
Breadth-first Search（廣度優(yōu)先搜索）
104. Maximum Depth of Binary Tree
class Solution {
public:
int maxDepth(TreeNode* root) {
if (!root) return 0;
int res = 0;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
++res;
int n = q.size();
for (int i = 0; i < n; ++i) {
TreeNode *t = q.front(); q.pop();
if (t->left) q.push(t->left);
if (t->right) q.push(t->right);
}
}
return res;
}
};
廣度優(yōu)先搜索是一種層次遍歷惯裕。實(shí)現(xiàn)一般都會(huì)借助隊(duì)列。根結(jié)點(diǎn)先入隊(duì)列，然后出隊(duì)列的同時(shí)祸穷，左右子樹(shù)再入隊(duì)列。重復(fù)這樣的過(guò)程便能完成整棵樹(shù)的層次遍歷勺三，下面是示意圖：
怎樣應(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面試與筆試-（十六）
