二叉树的深度与高度
二叉树的深度：从根节点到该节点的最长简单路径边的条数或节点数（取决于深度是否从1开始）
二叉树的高度：从该节点到叶子节点的最长简单路径边的条数或节点数（取决于高度是否从1开始）
104.二叉树的最大深度
思考
根据二叉树深度和高度的定义可知根节点的高度就是二叉树的最大深度。
二叉树的前序遍历：顺序是中左右，求二叉树的深度；
二叉树的后序遍历：顺序是左右中，求二叉树的高度；
递归
- 确定递归函数参数与返回值:
int maxDepth(*TreeNode root) - 递归的终止条件: 节点为空
- 单层递归处理逻辑：先求左子树深度，在求右子树深度，最后左右子树深度最大值。
func maxDepth(root *TreeNode) int {
if root == nil {
return 0
}
// 后序遍历
return 1 + max(maxDepth(root.Left), maxDepth(root.Right))
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
前序遍历的方法
func maxDepth(root *TreeNode) int {
if root == nil {
return 0
}
rlt := 0
var getDepth func(*TreeNode, int)
getDepth = func(node *TreeNode, depth int) {
// 前序遍历
if rlt < depth {
rlt = depth
}
if node.Left != nil {
getDepth(node.Left, depth+1)
}
if node.Right != nil {
getDepth(node.Right, depth+1)
}
}
getDepth(root, 1)
return rlt
}
迭代法
使用层序遍历求最大深度更容易理解，只需要在处理每层节点之前进行层数计数。
func maxDepth(root *TreeNode) int {
if root == nil {
return 0
}
depth := 0
queue := list.New()
queue.PushBack(root)
for queue.Len() > 0 {
length := queue.Len()
depth++ // 层数+1
for ; length > 0; length-- {
cur := queue.Remove(queue.Front()).(*TreeNode)
if cur.Left != nil {
queue.PushBack(cur.Left)
}
if cur.Right != nil {
queue.PushBack(cur.Right)
}
}
}
return depth
}
总结
求解二叉树的最大深度可以使用递归和迭代法， 在递归法中要明白是前序遍历还是后序遍历。
559. N 叉树的最大深度
思考
求N叉树的最大深度与二叉树的最大深度思路是一样的，下面直接贴出相关代码
递归
/**
* Definition for a Node.
* type Node struct {
* Val int
* Children []*Node
* }
*/
func maxDepth(root *Node) int {
if root == nil {
return 0
}
depth := 0
for i := 0; i < len(root.Children); i++ {
depth = max(maxDepth(root.Children[i]), depth)
}
return 1 + depth
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
迭代法
使用层序遍历
/**
* Definition for a Node.
* type Node struct {
* Val int
* Children []*Node
* }
*/
func maxDepth(root *Node) int {
if root == nil {
return 0
}
queue := list.New()
queue.PushBack(root)
depth := 0
for queue.Len() > 0 {
length := queue.Len()
depth++
for i := 0; i < length; i++ {
cur := queue.Remove(queue.Front()).(*Node)
for j := 0; j < len(cur.Children); j++ {
if cur.Children[j] != nil {
queue.PushBack(cur.Children[j])
}
}
}
}
return depth
}
111. 二叉树的最小深度
思考
求二叉树的最小深度就是求解根节点到叶子节点的距离，与二叉树的最大深度类似，需要注意的是：最小深度是从根节点到最近叶子节点的最短路径上的节点数量，因此我们需要遍历到叶子节点。
递归
- 确定递归函数的参数与返回值：
minDepth(root *TreeNode) - 递归的终止条件:
if root == nil; return 0 - 单层递归逻辑:
leftDepth := minDepth(root.Left) // 左 rightDepth := minDepth(root.Right) // 右 // 中 if root.Left == nil && root.Right != nil { return 1 + rightDepth } if root.Left != nil && root.Right == nil { return 1 + leftDepth }
完整代码如下：
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func minDepth(root *TreeNode) int {
// 后序遍历递归
if root == nil {
return 0
}
leftDepth := minDepth(root.Left) // 左
rightDepth := minDepth(root.Right) // 右
// 中
if root.Left == nil && root.Right != nil {
return 1 + rightDepth
}
if root.Left != nil && root.Right == nil {
return 1 + leftDepth
}
return 1 + min(leftDepth, rightDepth)
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
前序遍历
func minDepth(root *TreeNode) int {
if root == nil {
return 0
}
rlt := math.MaxInt32
var getdepth func(*TreeNode, int)
getdepth = func(node *TreeNode, depth int) {
// 递归结束条件
if node.Left == nil && node.Right == nil {
if rlt > depth {
rlt = depth
}
return
}
if node.Left != nil {
getdepth(node.Left, depth+1)
}
if node.Right != nil {
getdepth(node.Right, depth+1)
}
}
getdepth(root, 1)
return rlt
}
迭代法
求解最小的深度使用层序遍历依然适用, 从根节点一层一层向下遍历，当遇到左右孩子都为空时，就返回，此时的深度最小。
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func minDepth(root *TreeNode) int {
if root == nil {
return 0
}
queue := list.New()
queue.PushBack(root)
depth := 0
for queue.Len() > 0 {
length := queue.Len()
depth++
for ; length > 0; length-- {
cur := queue.Remove(queue.Front()).(*TreeNode)
if cur.Left == nil && cur.Right == nil {
return depth
}
if cur.Left != nil {
queue.PushBack(cur.Left)
}
if cur.Right != nil {
queue.PushBack(cur.Right)
}
}
}
return depth
}
总结
求二叉树的最小深度与最大深度的不同在于处理左右孩子为空的逻辑。
222. 完全二叉树的节点个数
参考：代码随想录
完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。
思考
求二叉树的节点数量，遍历完一整颗树即可得到。先求左子树节点数量再求右子树节点，最后将左右节点数相加。
使用后序遍历示例代码：
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func countNodes(root *TreeNode) int {
if root == nil {
return 0
}
leftCount := countNodes(root.Left)
rightCount := countNodes(root.Right)
return 1 + leftCount + rightCount
}
进阶
根据完全二叉树的性质可知，一个完全二叉树有两种情况：
- 满二叉树： 满二叉树计算节点数：\(2^n-1\)，根节点的深度为1
- 叶子节点没有满： 分别递归左孩子和右孩子，递归到一定深度一定会有左孩子或者右孩子是一颗满二叉树（单个节点也满足一颗满二叉树）
如何判断满二叉树：
递归向左遍历的深度等于递归向右遍历的深度时，说明是一颗满二叉树。
-
确定递归函数参数与返回值：
func countNodes(root *TreeNode) int，返回满二叉树的节点数。 -
递归的终止条件为：
if root == nil { return 0 } leftH, rightH := 0, 0 leftNode, rightNode := root.Left, root.Right for leftNode != nil { leftH++ leftNode = leftNode.Left } for rightNode != nil { rightH++ rightNode = rightNode.Right } if leftH == rightH { return 2<<leftH - 1 } -
单层递归逻辑：分别计算左子树与右子树的节点数，然后相加。
整体代码如下：
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func countNodes(root *TreeNode) int {
//完全二叉树的特性
if root == nil {
return 0
}
leftH, rightH := 0, 0
leftNode, rightNode := root.Left, root.Right
for leftNode != nil {
leftH++
leftNode = leftNode.Left
}
for rightNode != nil {
rightH++
rightNode = rightNode.Right
}
if leftH == rightH {
return 2<<leftH - 1
}
return 1 + countNodes(root.Left) + countNodes(root.Right)
}
总结
利用完全二叉树的特性可以判断是否是满二叉树，根据满二叉树的节点计算公式\(2^n-1\)计算总的节点数。
时间复杂度: \(O(logn*logn)\)
空间复杂度: \(O(logn)\)