Depth-first Search（深度優(yōu)先搜索）

104. Maximum Depth of Binary Tree

求二叉樹的最大深度問(wèn)題，經(jīng)典的深度優(yōu)先搜索
先給出代碼：

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (!root) return 0;
        //先遞歸計(jì)算左邊子樹的最大深度
        int l = 1+ maxDepth(root->left);
        //再遞歸計(jì)算右邊子樹的最大深度
        int r = 1+ maxDepth(root->right);
        //返回兩者的最大值
        return max(l,r); 
    }
};

為簡(jiǎn)單，我們僅以左子樹為例說(shuō)明，下面星星符號(hào)里的數(shù)字是函數(shù)的遞歸執(zhí)行順序

104.png

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í)，左右子樹再入隊(duì)列。重復(fù)這樣的過(guò)程便能完成整棵樹的層次遍歷，下面是示意圖：

104-廣度優(yōu)先.png

怎樣應(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面試與筆試-（十六）