104 二叉树的最大深度
用递归的写法。递归的思路是,当前树的深度=max(左子树深度, 右子树深度) + 1
111 二叉树的最小深度
对于上面这颗二叉树,离root最近的叶子节点是4,所以最小深度是3(路径1-2-4,有3个节点)。而如果我们直接把递归里的max改成min,由于root节点的左节点是None,那么最终的结果会是1。
其根本原因是,最小深度不是到某个节点没有左节点或右节点为止(这种节点不是叶子节点),而是到某个节点同时没有左右节点为止(这种节点才是叶子节点)。
所以在递归里,我们要判断是否当前节点的左子树或右子树为空。
(1)如果左子树为空,右子树不为空,那么最小深度由右子树决定。
(2)如果右子树为空,左子树不为空,那么最小深度由左子树决定。
(3)如果左右子树都不为空,那么最小深度由两者的最小值决定。(只有这种情况下才能把max直接改成min)
需要加上判断 左子树为空 右子树不空 那么最小高度由右子树决定
222 完全二叉树的节点个数
用深度优先的递归法,其核心思路是,当前树的节点数量=左子树节点数量+右子树节点数量+1,这个1代表的是中间节点的个数
标签:左子,03,右子,最小,二叉树,深度,节点 From: https://www.cnblogs.com/hook-thresh/p/17489848.html