543. Diameter Of Binary Tree

543. Diameter Of Binary Tree [Easy] 二叉树的直径

题干

Given the root of a binary tree, return *the length of the diameter of the tree*.

The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

The length of a path between two nodes is represented by the number of edges between them.

Example 1:

Input: root = [1,2,3,4,5]
Output: 3
Explanation: 3 is the length of the path [4,2,1,3] or [5,2,1,3].

Example 2:

Input: root = [1,2]
Output: 1

Constraints:

• The number of nodes in the tree is in the range [1, 104].
• -100 <= Node.val <= 100

解法

递归解法

核心思路：

• 将问题转换为求每个节点的左右子树高度之和，后序遍历

递归实现（返回节点高度，同时计算递归过程中各个节点的最长直径；这两者都是后序遍历，所以可以循只遍历一次）：

• 输入参数：Optional[TreeNode]
• 输出参数：int（高度）
• 终止条件：None节点的高度为0，返回它
• 单层核心逻辑：
  • 返回节点高度
  • 计算左节点的高度，计算右节点的高度
  • 取最大值+1，并返回
  • 更新全局最长直径

# 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.max_diameter = 0
        self.getHeight(root)
        return self.max_diameter
    
    def getHeight(self, node: Optional[TreeNode]) -> int:
        # 终止条件
        if node is None:
            return 0
        # 后序遍历
        left_h = self.getHeight(node.left)
        right_h = self.getHeight(node.right)
        self.max_diameter = max(left_h + right_h, self.max_diameter)
        return 1 + max(left_h, right_h)