LeetCode: 543 Diameter of Binary Tree

Given the root of a binary tree, the diameter of the tree is the length of the longest path between any two nodes in the 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

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

问题

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

例子

输入: root = [1,2,3,4,5]
输出: 3
解释: 最长的路径是 [4, 2, 1, 3] 或 [5, 2, 1, 3]，长度为 3。

Solution

Approach: Depth-First Search (DFS) / 深度优先搜索

The diameter of a binary tree can be found by recursively calculating the height of each subtree using Depth-First Search (DFS).
For each node, the longest path that passes through the node is the sum of the left subtree height and right subtree height. We calculate this for every node and keep track of the maximum diameter encountered.

Approach Explanation / 方法解释

Height Calculation: The height of a node is the maximum depth from that node to any leaf node.
Diameter Calculation: For each node, the diameter is calculated as left_height + right_height.
Recursion: Using DFS, we recursively calculate the height and update the diameter during the process.

Recurrence / 递推关系

diameter = max(diameter, left_height + right_height)
height = max(left_height, right_height) + 1

Implementation / 实现

Python

class Solution:
    def diameterOfBinaryTree(self, root: TreeNode) -> int:
        self.diameter = 0

        def dfs(node):
            if not node:
                return 0
            left_height = dfs(node.left)
            right_height = dfs(node.right)

            # Update the diameter
            self.diameter = max(self.diameter, left_height + right_height)

            return max(left_height, right_height) + 1

        dfs(root)
        return self.diameter

Explanation / 解释

Initialize Diameter Variable / 初始化直径变量
```
self.diameter = 0
```
- English: We initialize self.diameter to store the maximum diameter encountered during the DFS traversal.
- Chinese: 我们初始化 self.diameter 来存储在深度优先搜索过程中遇到的最大直径。
Depth-First Search (DFS) / 深度优先搜索 (DFS)
```
def dfs(node):
   if not node:
       return 0
```
- English: If the current node is None, return 0, indicating that the height of a null subtree is 0.
- Chinese: 如果当前节点为 None，返回 0，表示空子树的高度为 0。
Calculate Left and Right Subtree Heights / 计算左右子树的高度
```
left_height = dfs(node.left)
right_height = dfs(node.right)
```
- English: Recursively calculate the height of the left and right subtrees.
- Chinese: 递归计算左右子树的高度。
Update Diameter / 更新直径
```
self.diameter = max(self.diameter, left_height + right_height)
```
- English: Update the diameter by comparing the current diameter with the sum of left_height and right_height, which represents the longest path passing through the current node.
- Chinese: 通过比较当前直径和 left_height + right_height 的总和，更新直径，这代表经过当前节点的最长路径。
Return Node Height / 返回节点高度
```
return max(left_height, right_height) + 1
```
- English: Return the height of the current node, which is the maximum of the left and right heights plus one.
- Chinese: 返回当前节点的高度，即左右高度的最大值加一。
Return the Final Diameter / 返回最终直径
```
return self.diameter
```
- English: After completing the DFS traversal, return the maximum diameter found.
- Chinese: 在完成深度优先搜索后，返回找到的最大直径。

Complexity Analysis / 复杂度分析

Time Complexity / 时间复杂度: O(n), where n is the number of nodes in the tree. Each node is visited once.
Space Complexity / 空间复杂度: O(h), where h is the height of the tree, representing the recursion stack depth in the worst case.

Key Concept / 关键概念

Depth-First Search (DFS) / 深度优先搜索 (DFS): DFS is used to explore the tree from the root, calculate the height of each subtree, and update the diameter at each step.
Tree Diameter / 树的直径: The diameter is the longest path between any two nodes in the tree, which can be calculated by summing the heights of the left and right subtrees for each node.

Summary / 总结

English: The diameter of a binary tree can be efficiently calculated using DFS to recursively find the height of each node and update the diameter at each step.
Chinese: 通过使用深度优先搜索 (DFS) 递归地找到每个节点的高度，并在每一步更新直径，可以高效地计算二叉树的直径。

Tips / 提示

English: Practice problems involving trees and recursion to strengthen your understanding of DFS, and how to use recursive functions to solve tree-related problems.
Chinese: 练习涉及树和递归的问题，以加强对深度优先搜索 (DFS) 的理解，并学习如何使用递归函数来解决与树相关的问题。

5 More Similar Questions / 推荐5问题

Recommended Resources / 推荐资源

English: Practice problems involving DFS and tree traversal to better understand how to calculate tree metrics like height and diameter.
Chinese: 练习涉及深度优先搜索 (DFS) 和树遍历的问题，以更好地理解如何计算树的高度和直径等指标。

Diameter of Binary Tree – Leetcode 543 – Python by Neetcode

Post Views: 9

CODEBITWAVE