[Leetcode][python]二叉树的直径

悠悠 2022-05-16 06:29 186阅读 0赞

## 题目大意 ##

[https://leetcode-cn.com/problems/diameter-of-binary-tree/description/][https_leetcode-cn.com_problems_diameter-of-binary-tree_description]

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

## 解题思路 ##

二叉树的直径：二叉树中从一个结点到另一个节点最长的路径，叫做二叉树的直径

采用分治和递归的思想：根节点为root的二叉树的直径 = max(root-left的直径，root->right的直径，root->left的最大深度+root->right的最大深度+1)

分两种情况，1，最大直径经过根节点，则直径为左子树最大深度+右子树最大深度 2.如果不经过根节点，则取左子树或右子树的最大深度

## 代码 ##

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

## 总结 ##

[https_leetcode-cn.com_problems_diameter-of-binary-tree_description]: https://leetcode-cn.com/problems/diameter-of-binary-tree/description/

发表评论取消回复

表情：

评论列表（有 0 条评论，186人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode-543. 二叉树的直径

目录题目分析错误实例正确实例题目来源 [543. 二叉树的直径][543.] 题目分析 1.如何求得两个叶子

╰半橙微兮°/ 2024年03月27日 14:08/ 0 赞/ 94 阅读

相关 543. 二叉树的直径

打卡!!!每日一题今天给大家带来一道树类型的深度优先遍历题目。对于树类型的题目，无论怎么考无非就是考察前中后序遍历以及层次遍历。当然很多人想当然的认为树的考查只有深

本是古典何须时尚/ 2023年10月11日 18:35/ 0 赞/ 23 阅读

相关 543. 二叉树的直径【71】

> 难度等级：容易 > 上一篇算法： > > [199. 二叉树的右视图【111】][199. _111] > 力扣此题地址： > > [543. 二叉树的直径 - 力

短命女/ 2023年09月27日 18:14/ 0 赞/ 109 阅读

相关 leetcode543. 二叉树的直径

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

╰半橙微兮°/ 2023年07月06日 13:08/ 0 赞/ 25 阅读

相关 Leetcode 543. 二叉树的直径

Leetcode 543. 二叉树的直径 1、问题分析 2、问题解决 3、总结 1、问题分析题目链接：[https://leetcode-cn

小灰灰/ 2023年02月14日 03:10/ 0 赞/ 33 阅读

相关 543. 二叉树的直径

题目来源 [543. 二叉树的直径][543.] 题目描述 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_sha

╰半夏微凉°/ 2022年12月19日 11:39/ 0 赞/ 179 阅读

相关 leetcode543二叉树的直径

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

傷城~/ 2022年08月29日 10:58/ 0 赞/ 191 阅读

相关 [Leetcode][python]二叉树的直径

题目大意 [https://leetcode-cn.com/problems/diameter-of-binary-tree/description/][https_le

悠悠/ 2022年05月16日 06:29/ 0 赞/ 187 阅读

相关【LeetCode】543. 二叉树的直径

题目链接：[https://leetcode-cn.com/problems/diameter-of-binary-tree/description/][https_leetc

Dear 丶/ 2022年05月13日 17:29/ 0 赞/ 204 阅读

相关 LeetCode-543. 二叉树的直径

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

柔光的暖阳◎/ 2022年01月28日 17:57/ 0 赞/ 215 阅读