首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

如何找到二叉树的直径?

二叉树的直径是指任意两个节点之间的最长路径长度。要找到二叉树的直径,可以通过深度优先搜索(DFS)的方法来解决。

首先,需要定义一个全局变量max_diameter来记录最长路径的长度。然后,编写一个递归函数来遍历二叉树的每个节点,并计算以该节点为根节点的子树的高度。

递归函数的逻辑如下:

  1. 如果当前节点为空,返回0。
  2. 递归计算当前节点的左子树的高度,记为left_height。
  3. 递归计算当前节点的右子树的高度,记为right_height。
  4. 更新max_diameter,取左右子树高度之和与max_diameter的较大值。
  5. 返回左右子树高度的较大值加1,表示当前节点的高度。

最后,通过调用递归函数来计算二叉树的直径,最终得到的max_diameter即为所求。

以下是一个示例的代码实现(使用Python语言):

代码语言:txt
复制
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def find_diameter(root):
    if root is None:
        return 0

    max_diameter = 0

    def dfs(node):
        nonlocal max_diameter
        if node is None:
            return 0

        left_height = dfs(node.left)
        right_height = dfs(node.right)

        max_diameter = max(max_diameter, left_height + right_height)

        return max(left_height, right_height) + 1

    dfs(root)

    return max_diameter

这个算法的时间复杂度为O(n),其中n为二叉树的节点数。

推荐的腾讯云相关产品:无

页面内容是否对你有帮助?
有帮助
没帮助

相关·内容

LeetCode-543-二叉树直径

# LeetCode-543-二叉树直径 给定一棵二叉树,你需要计算它直径长度。一棵二叉树直径长度是任意两个结点路径长度中最大值。这条路径可能穿过也可能不穿过根结点。...示例1: 给定二叉树 1 / \ 2 3 / \ 4 5 返回 3, 它长度是路径 [4,2,1,3...**注意:**两结点之间路径长度是以它们之间边数目表示。 # 解题思路 方法1、DFS: 二叉树直径是不一定经过root节点,可能存在于每个子树中,所以需要遍历每个节点左右子树深度。...动态记录最大直径 直径 = max(左子树深度+右子树深度) 某节点子树深度 = max(某节点左子树深度,某节点右子树深度)+1 # Java代码 /** * Definition for a

21010

二叉树直径(LeetCode 543)

文章目录 1.问题描述 2.难度等级 3.热门指数 4.解题思路 参考文献 1.问题描述 给你一棵二叉树根节点,返回该树直径二叉树 直径 是指树中任意两个节点之间最长路径长度 。...所以解决该题需要先知道如何求解二叉树高度。 如果我们知道了左子树和右子树最大深度 l 和 r,那么该二叉树最大深度即为:max(l,r)+1。...知道了如何求解二叉树高度之后,那么在递归搜索过程中记录当前结点作为根结点最长路径。该最长路径就是整个二叉树最长路径。 注意,题目要求是最长路径上边数,而不是结点数,所以最后返回时要减一。...时间复杂度: O(n),其中 n 为二叉树结点数,即遍历一棵二叉树时间复杂度,每个结点只被访问一次。 空间复杂度: 递归函数分配栈空间为 O(logn),即二叉树高度。...二叉树直径- LeetCode

9910

LeetCode-543-二叉树直径

# LeetCode-543-二叉树直径 给定一棵二叉树,你需要计算它直径长度。一棵二叉树直径长度是任意两个结点路径长度中最大值。这条路径可能穿过也可能不穿过根结点。...示例1: 给定二叉树 1 / \ 2 3 / \ 4 5 返回 3, 它长度是路径 [4,2,1,3...**注意:**两结点之间路径长度是以它们之间边数目表示。 # 解题思路 方法1、DFS: 二叉树直径是不一定经过root节点,可能存在于每个子树中,所以需要遍历每个节点左右子树深度。...动态记录最大直径 直径 = max(左子树深度+右子树深度) 某节点子树深度 = max(某节点左子树深度,某节点右子树深度)+1 # Java代码 /** * Definition for a

18410

【每日leetcode】25.二叉树直径

可以将二叉树直径转换为:二叉树每个节点左右子树高度和最大值。 ——leetcode此题热评 前言 哈喽,大家好,我是一条。 糊涂算法,难得糊涂 Question 543....二叉树直径 难度:简单 给定一棵二叉树,你需要计算它直径长度。一棵二叉树直径长度是任意两个结点路径长度中最大值。这条路径可能穿过也可能不穿过根结点。 示例 : ?...返回 3, 它长度是路径 [4,2,1,3] 或者 [5,2,1,3]。 注意:两结点之间路径长度是以它们之间边数目表示。...先递归调用左儿子和右儿子求得它们为根子树深度 L和 R,则该节点为根子树深度即为max(L,R)+1 递归搜索每个节点返回最大值即可。...(node.left); int Right = depth(node.right); maxd=Math.max(Left+Right,maxd);//将每个节点最大直径

44860

二叉树直径

一、题目 给你一棵二叉树根节点,返回该树 直径二叉树 直径 是指树中任意两个节点之间最长路径 长度 。这条路径可能经过也可能不经过根节点 root 。...那么如何确定哪两个节点是值得去进行计算?或者那两个节点我们应该去进行计算。...所以,我们得出一个结论: 可能最大直径 = leftNode到rootNode距离 + rootNode到rightNode距离; 那么,因为二叉树也并不只有3个节点,如果节点很多的话,那么这个二叉树层级也就会越深...,那么下面我们其实如果能找到leftNode到rootNode距离最大值(或最深路径)以及找到rootNode到rightNode距离最大值(或最深路径),那么相加必然就是本题所要求解最大直径了。...以上就是本题解题思路,为了便于大家更加深入理解,下面我们以输入root = [1,2,3,4,5]为例,看一下是如何进行最大直径计算(图中省略了根节点深度和直径计算,大家自行脑补即可),请见下图所示

57950

​LeetCode刷题实战543:二叉树直径

今天和大家聊问题叫做 二叉树直径,我们先来看题面: https://leetcode-cn.com/problems/diameter-of-binary-tree/ Given the root...给定一棵二叉树,你需要计算它直径长度。一棵二叉树直径长度是任意两个结点路径长度中最大值。这条路径可能穿过也可能不穿过根结点。...示例 解题 思路一:不一定最长路径一定要穿过根节点,所以每个节点都要遍历,把每个节点作为根节点,然后,算出根节点左子树最大深度和右子树最大深度,把把左右子树最大深度加起来,作为暂时当前根节点最大路径长度...把所有节点作为根节点,比较所有根节点最大路径长度,选最大。...,左右深度相加即为当前子树直径,遍历完每一棵子树后最大那个直径即为二叉树直径

20910

直径

20 2 1 10 0 3 29 0 4 50 Sample Output Case 1: 100 Case 2: 80 这个题刚开始一直不理解,可能是对树直径比较陌生吧...只要从任意一个节点出发然后找到距离他最远节点,然后再让这个最远出发去找距离这个最远,这两个节点距离就是树直径!...每台新电脑都连接到一台先前安装电脑上。学校管理人员担心网络运行缓慢,希望知道第i台计算机需要发送信号最大距离si(即到最远计算机电缆长度)。您需要提供此信息。 ?...输入行中数字用空格分隔。 输出 对于每组样例,输出n行。第i行第i台计算机到其他计算机最大长度Si(1<=i<=n)。...这个一看见就直接蒙圈了Woc这咋搞,想了好久还是csdn了,从一个点出发寻找到距离它最远点,然后在从这个点出发寻找距离它最远点中间记录每个节点最远路程,这样算路径都是距离该节点最远路径,然后再从距离这个点最远点在进行

42920
领券