二叉树的直径

[编程题]二叉树的直径

热度指数：3222 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一颗二叉树，求二叉树的直径。

1.该题的直径定义为：树上任意两个节点路径长度的最大值

2.该题路径长度定义为：不需要从根节点开始，也不需要在叶子节点结束，也不需要必须从父节点到子节点，一个节点到底另外一个节点走的边的数目

3.这个路径可能穿过根节点，也可能不穿过

4.树为空时，返回 0

如，输入{1,2,3,#,#,4,5}，二叉树如下:

那么：

从4到5的路径为4=>3=>5，路径长度为2

从4到2的路径为4=>3=>1=>2，路径长度为3

如，输入{1,2,3,#,#,4,5,9,#,#,6,#,7,#,8}，二叉树如下:

那么路径长度最长为:7=>9=>4=>3=>5=>6=>8，长度为6

数据范围：节点数量满足 $0 \le n \le 100 \$

示例1

输入

{1,2,3,#,#,4,5}

输出

示例2

输入

{1,2,3,#,#,4,5,9,#,#,6,#,7,#,8}

输出

示例3

输入

{1,2,3}

输出

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

算法知识视频讲解

Python 3

Joy_9

class Solution:
    def diameterOfBinaryTree(self , root: TreeNode) -> int:
        # 递归+计算树的最大深度
        self.best=0
        def depth(root):
            if not root:
                return 0
            left=depth(root.left)
            right=depth(root.right)
            self.best=max(self.best,left+right)
            return max(left,right)+1
        
        de=depth(root)
        
        return self.best

发表于 2022-01-12 07:16:12 回复(0)