二叉树的最大深度

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

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

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

func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    return Max(maxDepth(root.Left), maxDepth(root.Right)) + 1
}

这是最简单的解法。

参考手把手带你刷二叉树（纲领篇） :: labuladong的算法小抄 (gitee.io)

二叉树的题目，要么通过分解问题，要么就是遍历二叉树。前者对应了回溯，后者对应动态规划。

而上面的解法是分解问题的解法。

通过遍历二叉树的解法应该怎么做呢？

var res int = 0
var depth int = 0

func maxDepth(root *TreeNode) int {
    traverse(root)
    return res
}

func traverse(node *TreeNode) {
    if node == nil {
        res = Max(depth, res)
        return
    }
    // 前序位置
    depth++
    traverse(node.Left)
    traverse(node.Right)
    // 后序位置
    depth--
}

这个解法应该很好理解，但为什么需要在前序位置增加 depth，在后序位置减小 depth？

因为前面说了，前序位置是进入一个节点的时候，后序位置是离开一个节点的时候，depth 记录当前递归到的节点深度，所以要这样维护。