实现二叉树的深度方式有两种,递归以及非递归。

①递归实现:

为了求树的深度,可以先求其左子树的深度和右子树的深度,可以用递归实现,递归的出口就是节点为空。返回值为0;

②非递归实现:

利用层次遍历的算法,设置变量level记录当前节点所在的层数,设置变量last指向当前层的最 后一个节点,当处理完当前层的最后一个节点,让level指向+1操作。设置变量cur记录当前层 已经访问的节点的个数,当cur等于last时,表示该层访问结束。

层次遍历在求树的宽度、输出某一层节点,某一层节点个数,每一层节点个数都可以采取类似 的算法。

树的宽度:在树的深度算法基础上,加一个记录访问过的层节点个数最多的变量max,在访问 每层前max与last比较,如果max比较大,max不变,如果max小于last,把last赋值给max;