二叉树的直径

[编程题]二叉树的直径

热度指数：3135 时间限制：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，点此查看相关信息

算法知识视频讲解

Python3

liangzhengjie

一个树状的动态规划

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param root TreeNode类 
# @return int整型
#
class Solution:
    def diameterOfBinaryTree(self , root: TreeNode) -> int:
        # write code here
        map = {}
        res = self.tranverse(root, map)
        res = self.tranverse1(root, map)
        return res
    
    def tranverse(self, root, map):
        if root is None:
            return 0
        if root in map:
            return map[root]

        left = 0
        if root.left is not None:
            left = self.tranverse(root.left, map) + 1
        
        right = 0
        if root.right is not None:
            right = self.tranverse(root.right, map) + 1

        res = max(left, right)
        map[root] = res
        return res

    def tranverse1(self, root, map):
        if root is None:
            return 0
        res = 0

        if root.left is not None:
            res += map[root.left] + 1

        if root.right is not None:
            res += map[root.right] + 1

        return max(self.tranverse1(root.left, map), self.tranverse1(root.right, map), res)

发表于 2024-05-13 23:32:18 回复(0)

Python3

danspace

class Solution:
    def diameterOfBinaryTree(self , root: TreeNode) -> int:
        # write code here 
        def height(root):
            # 返回该节点的深度
            if not root:
                return 0 
            return max(1 + height(root.left), 1 + height(root.right))
        l = []
        def dfs(root):
            # 遍历二叉树，将每个节点的直径放入列表
            if not root:
                return 
            # 直径 = 左子树深度 + 右子树深度
            diameter = height(root.left) + height(root.right)
            l.append(diameter)
            dfs(root.left)
            dfs(root.right)
        
        dfs(root)
        return max(l) if len(l) > 0 else 0

发表于 2023-04-27 12:09:11 回复(0)