每天进步一点点🤏

二叉树的最大深度

  • 619 字

二叉树的最大深度

题目

1
2
3
4
5
6
7
8
9
10
给定一个二叉树 root ，返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

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

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

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
思路:
判读树的左右节点是否至少存在其一,存在则深度加一,以子节点进行递归,返回最终深度

代码:
function maxDepth($root)
{
    return $this->depth($root);
}

function depth($node, $depth = 1)
{
    if (!$node){
        return 0;
    }

    // 不存在子节点,返回当前深度
    if (!$node->left && !$node->right) {
        return $depth;
    }

    return max($this->depth($node->right, $depth + 1), $this->depth($node->left, $depth + 1));
}