【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 = 0def dfs(root):if root is None:return -1l_len = dfs(root.left) + 1r_len = dfs(root.right) + 1self.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。