树

4_1二叉树的最大深度

给定一个二叉树?root?，返回其最大深度。

二叉树的?最大深度?是指从根节点到最远叶子节点的最长路径上的节点数。

Answer-

方法一：深度优先递归

核心 ：

n1 = maxdep(dp->left);

n2 = maxdep(dp->right);

return (n1>n2 ? n1:n2) + 1;?

方法二：广度优先遍历

核心 ：一边pop一边push，怎么知道要pop多少个呢？用一个int size;来记录上一层应该出多少个元素。pop上层元素前先记录该层总个数size，出一个则size--,一边出一边加其左右孩子，就解决了。总体思想是每次只让队列保留当前层的所有节点。

学会了：

C++队列的使用

//导入

include "queue.h"

//声明

Queue<datatype> queue_name;

//加入

queue_name.push(value);

//弹出-和stack一样不返回元素仅仅弹出

queue.pop;

//获取front指向元素

queue.front();

//判空

queue.empty();