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

悠悠 2022-05-16 06:29 174阅读 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 条评论，174人围观）

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

相关阅读

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

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

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

相关 543. 二叉树的直径

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

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

相关 leetcode543. 二叉树的直径

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

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

相关 Leetcode 543. 二叉树的直径

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

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

相关 543. 二叉树的直径

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

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

相关 leetcode543二叉树的直径

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

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

相关 leetcode 543. 二叉树的直径(python)

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

- 日理万妓/ 2022年05月20日 07:38/ 0 赞/ 194 阅读

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

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

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

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

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

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

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

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

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