每天进步一点点🤏

二叉树的直径

  • 1269 字

二叉树的直径

题目

1
2
3
4
5
6
7
8
9
10
11
12
给你一棵二叉树的根节点,返回该树的 直径 
二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 这条路径可能经过也可能不经过根节点 root 
两节点之间路径的 长度 由它们之间边数表示

示例 1：
输入：root = [1,2,3,4,5]
输出：3
解释：3 ,取路径 [4,2,1,3] 或 [5,2,1,3] 的长度

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

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
思路:
直径 = 左子树的最大深度和右子树的最大深度, 递归每个节点, 找到最大的直径

代码:
class TreeNode
{
    public $val = null;
    public $left = null;
    public $right = null;

    function __construct($val = 0, $left = null, $right = null)
    {
        $this->val   = $val;
        $this->left  = $left;
        $this->right = $right;
    }
}

private $ans;

/**
 * @param TreeNode $root
 *
 * @return Integer
 */
function diameterOfBinaryTree($root)
{
    if (!$root->left && !$root->right) {
        return 0;
    }

    $this->ans = 1;
    $this->depth($root);

    return $this->ans;
}

private function depth($node)
{
    if (!$node) {
        return 0;
    }

    // 左子树的最大深度
    $left = $this->depth($node->left);
    // 右子树的最大深度
    $right = $this->depth($node->right);
    // 最大直径 = 左子树最大深度 + 右子树最大深度
    $this->ans = max($this->ans, $left + $right);

    // 左右子树较大一边的深度+1 = 当前节点的最大深度
    return max($left, $right) + 1;
}