代码随想录算法训练营|day16

104.二叉树的最大深度

最大深度：根节点到最远叶子节点的最长路径上的节点个数
(1)递归：max(左子树高度，右子树高度）+ 1

func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    return max(maxDepth(root.Left), maxDepth(root.Right)) + 1
}
1
2
3
4
5
6

(2)层序遍历：创建辅助队列

1. 先压入头节点
2. 若队列不为空，遍历当前层节点，并判断其左右节点是否存在，若存在将其压入栈中，结束后深度+1

func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    depth := 0
    curQueue := []*TreeNode{root}
    for len(curQueue) > 0 {
        nextQueue := []*TreeNode{}
        for _, node := range curQueue {
            if node.Left != nil {
                nextQueue = append(nextQueue, node.Left)
            }
            if node.Right != nil {
                nextQueue = append(nextQueue, node.Right)
            }
        }
        depth++
        curQueue = nextQueue
    }
    return depth
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

559.n叉树的最大深度

只能说与二叉树模板一样

(1)递归：所有孩子节点子树的最大高度+1

func maxDepth(root *Node) int {
    if root == nil {
        return 0
    }
    depth := 0
    for _, child := range root.Children {
        if childDepth := maxDepth(child); childDepth > depth {
            depth = childDepth
        }
    }
    return depth + 1
}
1
2
3
4
5
6
7
8
9
10
11
12

(2)层序遍历

func maxDepth(root *Node) int {
    if root == nil {
        return 0
    }
    depth := 0
    curQueue := []*Node{root}
    for len(curQueue) > 0 {
        nextQueue := []*Node{}
        for _, node := range curQueue {
            if node.Children != nil {
                for _, child := range node.Children {
                    nextQueue = append(nextQueue, child)
                }
            }
        }
        depth++
        curQueue = nextQueue
    }
    return depth
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

111.二叉树的最小深度

最小深度：根节点到最近叶子节点的最短路径上的节点个数
左右子树同时为空时候的节点高度的最小值 + 1
(1)递归
若左、右子树有一个为空，则返回不为空的子树的最小深度；若都不为空，返回左右子树中最小深度

func minDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    if root.Left != nil && root.Right == nil {
        return 1 + minDepth(root.Left)
    }
    if root.Right != nil && root.Left == nil {
        return 1 + minDepth(root.Right)
    }
    return min(minDepth(root.Left),minDepth(root.Right)) + 1
}
1
2
3
4
5
6
7
8
9
10
11
12

(2)层序遍历
若该层节点存在左右子树都为空，返回深度，否则继续遍历

func minDepth(root *TreeNode) int {
    depth := 0
    if root == nil {
        return depth
    }
    curQueue := []*TreeNode{root}
    for len(curQueue) > 0 {
        depth++
        nextQueue := []*TreeNode{}
        for _, node := range curQueue {
            if node.Left == nil && node.Right == nil {
                return depth
            }
            if node.Left != nil {
                nextQueue = append(nextQueue, node.Left)
            }
            if node.Right != nil {
                nextQueue = append(nextQueue, node.Right)
            }
        }
        curQueue = nextQueue
    }
    return depth
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

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

(1)递归：和求最大深度方法一样。【左右子树高度最大】【左右子树节点数和】

func countNodes(root *TreeNode) int {
    if root == nil {
        return 0
    }
    return countNodes(root.Left) + countNodes(root.Right) + 1
}
1
2
3
4
5
6

(2)层序遍历：和求最大深度方法一样，最大深度在每层遍历时depth++，节点个数则是在遍历弹出节点时，count++

func countNodes(root *TreeNode) int {
    if root == nil {
        return 0
    }
    count := 0
    curQueue := []*TreeNode{root}
    for len(curQueue) > 0 {
        nextQueue := []*TreeNode{}
        for _, node := range curQueue {
            if node.Left != nil {
                nextQueue = append(nextQueue, node.Left)
            }
            if node.Right != nil {
                nextQueue = append(nextQueue, node.Right)
            }
            count += 1
        }
        curQueue = nextQueue
    }
    return count
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

代码随想录文章详解

104.二叉树的最大深度
11.二叉树的最小深度
222.完全二叉树的节点个数

总结

今天做起来轻松多了，开心