104.二叉树的最大深度

文档和视频讲解：代码随想录(programmercarl.com)

状态：ac

用时：1h

思路：就是求得左右子树的最大深度，递归的返回值是该节点下的最大深度，参数是该节点的指针，终止条件为指针为空，此时返回0。递归逻辑为获取左右子树的深度取最大值，然后加一。迭代的思想是用层序遍历，每一层深度加一。

代码：

图1 迭代

图2 递归

图3 递归（精简）

111.二叉树的最小深度

文档和视频讲解：代码随想录(programmercarl.com)

状态：迭代ac，递归未ac

用时：1h

思路：如果用层序遍历，思路比较简单，一层层访问，当第一次遇到叶节点，即没有左右儿子的节点的时候，表示是最小深度。递归的方法，在递归逻辑上不同于最大深度。如果按照左右子树两边比较谁的树深度更小来递归的话，无法识别当节点只有左子树或者右子树的情况，这个时候会把最小深度计算为1(把当前节点当成了叶节点)。因此要识别只有单边的时候的树。

代码：

图4 递归

图5 层序

222.完全二叉树的节点个数

文档和视频讲解：代码随想录(programmercarl.com)

状态：普通二叉树方法ac，完全二叉树的方法未ac

用时：1h

思路：普通二叉树的递归方法是左右子树的节点数量加起来再加一就可，迭代方法就是层序遍历的同时把队列的每一层节点数量加上即可。完全二叉树的方法中，完全二叉树有两种情况，一种是满二叉树，一种是最后一层没有满。在计算第二种情况节点个数的时候，分别递归左右子节点到一定深度会有节点的左或右子树是满二叉树，此时计算该子树可以用满二叉树的公式，而不用递归时一个一个节点算。

图6 满二叉子树

    那么计算此时节点的树是否是满二叉树，可以根据最左边的深度和最右边的深度是否相等来看。

图7 左右相等

图8 左右不等

图9 该情况虽然相等，但不是满，也不是完全二叉树

代码：

图10 完全二叉树的方法