LeetCode二叉树的直径资源-CSDN文库

117 浏览量 2020-12-22 05:06:45 上传评论收藏 53KB PDF 举报

资源推荐

资源详情

资源评论

LeetCode 二叉树的直径二叉树的直径

文章目录文章目录二叉树的直径题目解题思路代码实现实现结果

二叉树的直径二叉树的直径

题目来源：https://leetcode-cn.com/problems/diameter-of-binary-tree/

题目题目

给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过

根结点。

示例示例 :

给定二叉树

1

/ \

2 3

/ \

4 5

返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。

注意：两结点之间的路径长度是以它们之间边的数目表示。

解题思路解题思路

这里需要注意，二叉树的直径（最长路径），有可能不经过根节点。如下图所示：

在这里，求二叉树的直径，即是求最长路径。先判断问题是否划分为子问题。其实二叉树路径的问题，就是选择问题：

1

/ \

2 3

1. [左] 2 - 1

2. [右] 3 - 1

3. [左中右]，2 - 1 - 3

根据上面的解析，那么现在将问题划分为：

二叉树最长路径 = max{[左]，[右]，[左中右]}

其中 [左]，[右]，这两种情况可以用递归进行求解，因为叶子节点路径为 0，往上走，例如 2 - 1，长度 + 1，也就是左右节点递

归返回值 + 1。

而 [左中右] 这种情况情况，其实就是左 + 右。

代码实现代码实现

class Solution:

def diameterOfBinaryTree(self, root: TreeNode) -> int:

self.ans = 0

def diameter_of_binary_tree(node, ans):

# 递归出口

if not node:

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余1页未读，立即下载

内容反馈

weixin_38527978

粉丝: 5
资源: 900

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈

feedback-tip