二叉树的最大深度

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点

深度优先

递归方式

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    return max(maxDepth(root.Left), maxDepth(root.Right)) + 1
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

通过递归的方式，深度优先搜索，如果知道了左子树，右子树的最大深度，l,r

则树的最大深度是max(l,r)+1

时间on
空间o高度

广度优先

遍历方式

func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    // 队列，并加入第一个节点
    queue := []*TreeNode{}
    queue = append(queue, root)
    ans := 0
    // 遍历队列
    for len(queue) > 0 {
    	// 获取当前队列长度，第一层是1
        sz := len(queue)
        // 遍历，出队，长度减1，第一层遍历完，结果加一
        for sz > 0 {
        	// 将树的每一层，都放进队列
            node := queue[0]
            // 队列先进先出
            queue = queue[1:]
            // 将队列的左右儿子加入，也就是下一层
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
            sz--
        }
        // 结果加一，上一层遍历完，sz=0，队列加入了下一层的值，继续遍历下一层
        ans++
    }
    return ans
}