二叉树的直径

解题思路

直径的计算方式

二叉树的直径 是 任意两个节点间最长路径的边数。该路径的长度等于路径上的节点数 - 1。

关键点分析

• 任意两个节点的最长路径 必定是某个节点的 左子树最深节点到右子树最深节点 之间的路径。
• 深度优先搜索（DFS） 可以帮助我们计算每个节点的左右子树最大深度。

Leetcode 40.二叉树的直径-原题链接

题目内容

给你一棵二叉树的根节点，输出该树的直径 。

二叉树的 直径是指树中任意两个节点之间最长路径的 长度。这条路径可能经过也可能不经过根节点 $root$ 。

两节点之间路径的长度 由它们之间边数表示。

输入描述

一行包含二叉树的序列化数组，节点值之间用空格隔开，空节点用null表示。

输出描述

输出该二叉树的直径，即最长路径上的边数。

样例1

输入

1 2 3 4 5

输出

3

说明

$3$ ，取路径$[4,2,1,3]$ 或$[5,2,1,3]$ 的长度。

样例2

输入

1 2

输出

1

提示

• 树中节点数目在范围 $[1, 10^4]$ 内
• $-100 <= Node.val <= 100$