0543：二叉树的直径

Ian

2016-06-26 约 285 字预计阅读 1 分钟次阅读

力扣第 543 题

题目

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

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

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

示例 1：

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

示例 2：

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

提示：

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

相似问题：

分析

递归返回节点的高度
递归过程中，根据左右子树的高度，即可求出经过该节点的最长路径

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        def dfs(u):
            if not u:
                return 0
            l,r = dfs(u.left),dfs(u.right)
            self.res = max(self.res,l+r)
            return max(l,r)+1
        self.res = 0
        dfs(root)
        return self.res

51 ms

目录

0543：二叉树的直径

题目

分析

解答