怎样应对IT面试与笔试-（九）

Depth-first Search（深度优先搜索）

104. Maximum Depth of Binary Tree

求二叉树的最大深度问题，经典的深度优先搜索
先给出代码：

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (!root) return 0;
        //先递归计算左边子树的最大深度
        int l = 1+ maxDepth(root->left);
        //再递归计算右边子树的最大深度
        int r = 1+ maxDepth(root->right);
        //返回两者的最大值
        return max(l,r); 
    }
};

为简单，我们仅以左子树为例说明，下面星星符号里的数字是函数的递归执行顺序

104.png

Breadth-first Search（广度优先搜索）

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;
    }
};

广度优先搜索是一种层次遍历。实现一般都会借助队列。根结点先入队列，然后出队列的同时，左右子树再入队列。重复这样的过程便能完成整棵树的层次遍历，下面是示意图：

104-广度优先.png

怎样应对IT面试与笔试-（一）
怎样应对IT面试与笔试-（二）
怎样应对IT面试与笔试-（三）
怎样应对IT面试与笔试-（四）
怎样应对IT面试与笔试-（五）
怎样应对IT面试与笔试-（五-1）
怎样应对IT面试与笔试-（六）
怎样应对IT面试与笔试-（七）
怎样应对IT面试与笔试-（八）
怎样应对IT面试与笔试-（九）
怎样应对IT面试与笔试-（十）
怎样应对IT面试与笔试-（十一）
怎样应对IT面试与笔试-（十二）
怎样应对IT面试与笔试-（十三）
怎样应对IT面试与笔试-（十四）
怎样应对IT面试与笔试-（十五）
怎样应对IT面试与笔试-（十六）