首页 > 试题广场 >

二叉树的直径

[编程题]二叉树的直径
  • 热度指数:3121 时间限制: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

数据范围:节点数量满足
示例1

输入

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

输出

3
示例2

输入

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

输出

6
示例3

输入

{1,2,3}

输出

2

说明:本题目包含复杂数据结构TreeNode,点此查看相关信息
头像 君无颜
发表于 2022-02-03 23:18:38
简单的递归就可以解决 核心 是要明白递归的判断要素:以当前节点为头结点的树,直径就是左右两个子树的高度相加,故有三个情况 以 root 为头结点的树,最大直径就是左右两个子树的高度相加 左子树的直径是以 root->left 为头结点的树,最大直径同理 右子树的直径是以 root- 展开全文
头像 代码界的小白
发表于 2022-02-26 14:19:19
二叉树的直径 给定一颗二叉树,求二叉树的直径。 1.该题的直径定义为:树上任意两个节点路径长度的最大值 2.该题路径长度定义为:不需要从根节点开始,也不需要在叶子节点结束,也不需要必须从父节点到子节点,一个节点到底另外一个节点走的边的数目 3.这个路径可能穿过根节点,也可能不穿过 4.树为空时,返回 展开全文
头像 小小小明哥
发表于 2022-01-19 18:19:14
典型的树形BP问题,一般想好要跟左右子树拿什么信息,然后自定义结构体,然后就分析取值的问题就好 第一种情况是:如果左右子树的高度和大于左右子树的最大直径,则应该取左右子树的高度和。 第二种情况是:如果左右子树的高度和小于左右子树的最大直径,则取左右子树较大的直径 /** * struct Tr 展开全文
头像 倔强小头
发表于 2021-11-26 19:02:51
import java.util.*; /* public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; 展开全文
头像 extern
发表于 2024-02-06 18:47:05
package main import ( . "nc_tools" ) /* * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ /** * 展开全文
头像 fred-coder
发表于 2022-01-06 17:45:33
由于求的是树的边的最长长度,则递归过程由左 -> 右 -> 根 顺序进行,并在递归过程中记录 左子树直径 和 右子树直径的和的最大值 # class TreeNode: # def __init__(self, x): # self.val = x # 展开全文
头像 1813004745
发表于 2022-02-21 19:56:51
边去递归边记录 import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * public TreeNo 展开全文
头像 extern
发表于 2024-02-06 11:47:22
/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) { 展开全文
头像 extern
发表于 2024-02-06 11:53:34
/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) { 展开全文
头像 牛客82035003号
发表于 2022-04-10 21:22:25
在用递归求左右子树的高度的同时,就将左右子树的高度之和与max比较,并持续更新max,最后的max即为两个结点之间的最大距离。 int max = 0; //max作为全局变量,不断在更新 int depth(struct TreeNode*& 展开全文