神刀安全网

怎样应对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);      } }; 

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

怎样应对IT面试与笔试-(九)

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

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

怎样应对IT面试与笔试-(九)

104-广度优先.png

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

转载本站任何文章请注明:转载至神刀安全网,谢谢神刀安全网 » 怎样应对IT面试与笔试-(九)

分享到:更多 ()