PeterQwQ
0%

Leetcode 543 二叉树的直径

发表于

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

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

对于一个节点而言，它的直径等于左子树的深度加上右子树的深度。因此，我们可以递归地求出每个节点的直径，取最大值即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        self.ans = 0
        def depth(node):
            if not node:
                return 0
            left_depth = depth(node.left)
            right_depth = depth(node.right)
            self.ans =  max(left_depth+right_depth+1, self.ans) 
            return max(left_depth, right_depth) + 1

        depth(root)
        return self.ans - 1