最大/小深度

max(maxDepth(root-left),maxDepth(root-right))1;}

终止条件为root

而递归的逻辑是我们需要在根节点的左子树和右子树中选最大值所以这里用maxx,y返回。

当递归到空节点开始返回一开始返回0后面逐渐1…到根节点就得到这颗子树的高度。

层序遍历

qu.front();qu.pop();if(node-left

nullptr)qu.push(node-left);if(node-right

nullptr)qu.push(node-right);}ans;}return

ans;}

};这里用的是层序遍历也即是广度优先对每一层的结点进行遍历然后同时ans

最小深度

当root为空则当前高度为0当root的左右子节点均为空则当前为叶子结点高度为1如果左右子节点有一个为空则m_left和m_right必有一个为0则直接返回两者相加1最后一种情况则是左右子节点均不为空则返回左右子树深度小的

class

?m_leftm_right1:min(m_right,m_left)1;}

};层序遍历

相比递归BFS要简单的多我们只需要找到第一个叶子节点然后返回即可找不到没关系继续遍历下一层。

class

qu.front();qu.pop();if(cur-left

nullptr

nullptr)qu.push(cur-left);if(cur-right

nullptr)qu.push(cur-right);}ans;}return

ans;}

};注意的是ans一开始初始化为1是因为根节点自身便带有高度只有空结点会为0。