543. 二叉树的直径

Difficulty
easy
Tags
二叉树
URL
https://leetcode-cn.com/problems/diameter-of-binary-tree/
Star
给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
示例 : 给定二叉树
          1
         / \
        2   3
       / \
      4   5
返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
注意：两结点之间的路径长度是以它们之间边的数目表示。

法1 递归

思路
类似于
🛎️
124. 二叉树中的最大路径和
124是求最大路径，本题是求路径长度
递归函数dp(root)定义：经过当前root节点，且最多使用一个子树。那么有
if root is None:
		LP(root) =  -1
else:
			LP(root) = 1 + max(LP(root.left), LP(root.right))
ans = max(ans, 2+LP(root.left)+LP(root.right)
题解
# 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: TreeNode) -> int:
        self.res = 0
        self.preOrder(node=root)
        return self.res
    def preOrder(self, node):
        if node is None:
            return -1
        l = self.preOrder(node.left) + 1
        r = self.preOrder(node.right) + 1
        self.res = max(l+r, self.res)
        return max(l, r)