【leetcode】543. 二叉树的直径

题目

543. 二叉树的直径

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

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

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

题解

思路：找到左边最长和右边最长

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def diameterOfBinaryTree(self, root):
        """
        :type root: Optional[TreeNode]
        :rtype: int
        """
        self.ans = 0
        def dfs(root):
            if root is None:
                return -1
            
            l_len = dfs(root.left) + 1
            r_len = dfs(root.right) + 1
            self.ans = max(self.ans, l_len + r_len)
            return max(l_len, r_len)
        dfs(root)
        return self.ans   

解释

假设我们有以下的二叉树：

     1
    / \
   2   3
  / \  
 4   5

步骤 1: 初始调用
diameterOfBinaryTree(root) 调用 dfs(root)，即传入根节点 1。

步骤 2: 递归计算深度

• 对节点 1：

  • 左子树：递归调用 dfs(root.left)，即节点 2。

• 对节点 2：

  • 左子树：递归调用 dfs(root.left)，即节点 4。

    • 节点 4 是叶子节点，因此返回 0。

  • 右子树：递归调用 dfs(root.right)，即节点 5。

    • 节点 5 是叶子节点，因此返回 0。

  • 对节点 2：l_len = 0 + 1 = 1，r_len = 0 + 1 = 1，self.ans = max(0, 1 + 1) = 2，返回 max(1, 1) = 1。

• 对节点 1：

  • 左子树：返回节点 2 的深度 1。

  • 右子树：递归调用 dfs(root.right)，即节点 3。

    • 节点 3 是叶子节点，因此返回 0。

  • 对节点 1：l_len = 1 + 1 = 2，r_len = 0 + 1 = 1，self.ans = max(2, 2 + 1) = 3，返回 max(2, 1) = 2。

步骤 3: 返回结果
最终返回 self.ans = 3，表示二叉树的直径为 3，即从节点 4 到节点 5，通过节点 2 再到节点 1，该路径包含 3 个节点。