LeetCode-104.二叉树的最大深度

二叉树#

给定一个二叉树 root ，返回其最大深度。

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

示例 1：

1
输入：root = [3,9,20,null,null,15,7]
2
输出：3

示例 2：

1
输入：root = [1,null,2]
2
输出：2

递归的解法

递归这种题有时候就是很傻逼和神奇，就像这题和汉谟拉比，不同的是这题从逻辑上可以从下往上推出来，汉谟拉比很麻烦

1
/**
2
 * Definition for a binary tree node.
3
 * type TreeNode struct {
4
 *     Val int
5
 *     Left *TreeNode
6
 *     Right *TreeNode
7
 * }
8
 */
9
func maxDepth(root *TreeNode) int {
10
    if root == nil {
11
        return 0
12
    }
13
    leftHeight := maxDepth(root.Left)
14

15
    rightHeight := maxDepth(root.Right)
16

17
    return max(leftHeight, rightHeight) + 1
18
}