题目大意 https://leetcode-cn.com/problems/diameter-of-binary-tree/description/ 给定一棵二叉树，你需要计算它的直径长度。...一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。...解题思路 二叉树的直径：二叉树中从一个结点到另一个节点最长的路径，叫做二叉树的直径 采用分治和递归的思想：根节点为root的二叉树的直径 = max(root-left的直径，root->right的直径...，root->left的最大深度+root->right的最大深度+1) 分两种情况，1，最大直径经过根节点，则直径为左子树最大深度+右子树最大深度 2.如果不经过根节点，则取左子树或右子树的最大深度...root.right) self.ans = max(self.ans, left + right) return max(left, right) + 1
二叉树直径的定义：二叉树中路径的最大长度 二叉树中路径的最大长度，可以理解所有节点的左右子树高度之和的最大值。...假设二叉树有n个节点，编号为{a1,a2,…,an}, 其对应的左右子树的高度之和为H = {h1,h2,h3,…,hn}, 则该二叉树的直径为max(H)。...struct node { int val; node *left, *right; }; int ans = 0;// 用于维护任意节点左右子树高度和的最大值 //dfs()函数的返回值是当前节点的高度...root->left); int right = dfs(root->right); ans = max(ans, left+right); return max(right, left) + 1;
# LeetCode-543-二叉树的直径 给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。...示例1： 给定二叉树 1 / \ 2 3 / \ 4 5 返回 3, 它的长度是路径 [4,2,1,3...] 或者 [5,2,1,3]。...**注意：**两结点之间的路径长度是以它们之间边的数目表示。 # 解题思路 方法1、DFS： 二叉树的直径是不一定经过root节点的，可能存在于每个子树中，所以需要遍历每个节点的左右子树深度。...动态记录最大的直径 直径 = max(左子树深度+右子树深度) 某节点子树的深度 = max(某节点左子树深度，某节点右子树深度)+1 # Java代码 /** * Definition for a
一 题目： 二 思路： 分析下，二叉树的最长路径某个结点的左孩子最大深度加右孩子的最大深度 我们只需要找出每一个节点的 左子树最大深度 + 右子树最大深度 的值，然后不断更新全局变量max 就行了...代码： class Solution { int max; public int diameterOfBinaryTree(TreeNode root) { //分析下，二叉树的最长路径某个结点的左孩子最大深度加右孩子的最大深度...max=0; dfs(root); return max; } /** * 返回树的深度 */ private...int lDeep= dfs(root.left); //右子树的深度 int rDeep= dfs(root.right); max=Math.max...(max,lDeep+rDeep); return Math.max(lDeep,rDeep)+1; } }
文章目录 1.问题描述 2.难度等级 3.热门指数 4.解题思路 参考文献 1.问题描述 给你一棵二叉树的根节点，返回该树的直径 。 二叉树的 直径 是指树中任意两个节点之间最长路径的长度 。...所以解决该题需要先知道如何求解二叉树的高度。 如果我们知道了左子树和右子树的最大深度 l 和 r，那么该二叉树的最大深度即为：max(l,r)+1。...具体而言，在计算当前二叉树的最大深度时，可以先递归计算出其左子树和右子树的最大深度，然后在 O(1) 时间内计算出当前二叉树的最大深度。递归在访问到空节点时退出。...时间复杂度： O(n)，其中 n 为二叉树的结点数，即遍历一棵二叉树的时间复杂度，每个结点只被访问一次。 空间复杂度： 递归函数分配栈空间为 O(logn)，即二叉树的高度。...二叉树的直径- LeetCode
可以将二叉树的直径转换为：二叉树的每个节点的左右子树的高度和的最大值。 ——leetcode此题热评 前言 哈喽，大家好，我是一条。 糊涂算法，难得糊涂 Question 543....二叉树的直径 难度：简单 给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。 示例 : ?...返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。 注意：两结点之间的路径长度是以它们之间边的数目表示。...先递归调用左儿子和右儿子求得它们为根的子树的深度 L和 R，则该节点为根的子树的深度即为max(L,R)+1 递归搜索每个节点返回最大值即可。...(左子树深度+右子树深度)当前最大值比较并取大者 return Math.max(Left,Right)+1;//返回节点深度 } } Result 复杂度分析 时间复杂度：
1. 题目 给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。...示例 : 给定二叉树 1 / \ 2 3 / \ 4 5 返回 3, 它的长度是路径 [4,2,1,3...] 或者 [5,2,1,3]。...注意：两结点之间的路径长度是以它们之间边的数目表示。...maxDiameter); int right = diameter(root->right,maxDiameter); int curMax = left+right;//包含当前根节点的直径为
left = dfs(root->left); int right = dfs(root->right); int depth = max(left, right) + 1;
一、题目 给你一棵二叉树的根节点，返回该树的 直径 。 二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。...二、示例 2.1> 示例 1： 图片 【输入】root = [1,2,3,4,5] 【输出】3 【解释】3 ，取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。...2.2> 示例 2： 【输入】root = [1,2] 【输出】1 提示： 树中节点数目在范围 [1, 10^4] 内 -100 <= Node.val <= 100 三、解题思路 根据题目描述，我们要获得二叉树中任意两个节点的最大直径...所以，我们得出一个结论： 可能的最大直径 = leftNode到rootNode的距离 + rootNode到rightNode的距离； 那么，因为二叉树也并不只有3个节点，如果节点很多的话，那么这个二叉树的层级也就会越深...以上就是本题的解题思路，为了便于大家更加深入的理解，下面我们以输入root = [1,2,3,4,5]为例，看一下是如何进行最大直径计算的（图中省略了根节点的深度和直径的计算，大家自行脑补即可），请见下图所示
二叉树的直径 - 力扣（LeetCode） 要找两个节点之间最多的边数，这个最多的边数必定是某个节点的左右子树的深度之和，因此递归计算每个子树的深度，过程中记录最大和即可 class Solution...left); int R = depth(root->right); ans = max(ans, L + R); return max(L, R) + 1;
今天和大家聊的问题叫做 二叉树的直径，我们先来看题面： https://leetcode-cn.com/problems/diameter-of-binary-tree/ Given the root...给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。...(root->right))+1; } void preOrder(TreeNode *root)//遍历每个节点，把遍历到的每个节点作为根节点 { if (!...，左右深度相加即为当前子树的直径，遍历完每一棵子树后最大的那个直径即为二叉树的直径。...right_depth+1); } }; 好了，今天的文章就到这里，如果觉得有所收获，请顺手点个在看或者转发吧，你们的支持是我最大的动力 。
1. 简介 树中所有简单路径的最大值即为树的直径，可以通过两次 DFS 或者树形 DP 在 时间内求解。 2....证明 假设结点 和 之间唯一的简单路径为树的直径， 表示结点 和 之间的唯一的简单路径的长度。...若该最远点 不是树的直径的一个端点，则对于当前根结点 来说： 如果 或 二者有一个不与 在同一个子树（假设为 ），则由于 与 为直径而 不是直径的端点矛盾。...代码 【注】以下模板均是基于无权树求树的直径，有权树只需在前向星中记录一下边权，然后更新结点高度/深度不是 + 1 而是 + 对应边权即可。...} } } diameter = max(diameter, h1+h2); return h1; } // 求解树的直径
求一棵树的直径的方法就是，从一个顶点出发，找到离它最远的顶点s，然后从顶点s出发，找离他最远的节点t.那么，s、t之间的距离就是树的直径。...对于加权无向树来说，树的直径就是s、t之间的路径上的边的权值相加。...tmp2; for (int i = 0; i 1; ++i) { cin >> s >> t >> w; tmp1.from = s;...tmp1.to = t; tmp1.weight = tmp2.weight = w; tmp2.from = t; tmp2.to = s;...vec[s].push_back(tmp1); vec[t].push_back(tmp2); } bfs(0); int m = -1, v; for
1.树的直径的求法不是很难，两遍DFS，树的直径又称为最长路，没看到树的直径的裸题，除了饭店的那个题，讲的是有一家饭店在一个图中，饭店的送餐时间与最远的送餐距离成正比，求饭店的修建位置使得饭店的送餐时间最短...，那么这个题就是说在图中赵找一条最长路，将饭店建在最长路的中心，这个题也是CCPC2019网络赛的一个题，几乎一样的模板，但是这个知识点常与树形DP一起出现，什么添边，什么附加条件，但是离不开最长路两边
以上为两边DFS求树的直径的过程，看完之后比较好理解算法实现过程，个人感觉两次DFS比树形DP要简单的多了，但还是将两种方法。...#include #include using namespace std; //maxv：源点能到的最远点，maxdis:最远点对应的距离, const...; for (int i = 1; i <= e; i++) { cin >> u >> v >> w; add(u, v, w), add(v, u, w); } dfs(1, -1,...0); //从结点1开始遍历，找到最远点maxv及对应的最远距离maxdis maxdis = 0; cout 直径的第一个端点 dfs(maxv, -1,...0);//从结点maxv开始遍历，找到最远点对应的距离maxdis cout 的直径 cout 的直径的第二个端点
木又连续日更第98天（98/100） ---- 木又的第142篇leetcode解题报告 二叉树类型第32篇解题报告 leetcode第543题：二叉树的直径 https://leetcode-cn.com.../problems/diameter-of-binary-tree/ ---- 【题目】 给定一棵二叉树，你需要计算它的直径长度。...一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。...示例 : 给定二叉树 1 / \ 2 3 / \ 4 5 返回 3, 它的长度是路径 [4,2,1,3...] 或者 [5,2,1,3]。
1.题目 难度：简单 给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。...示例 : 给定二叉树 1 / \ 2 3 / \ 4 5 返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3...---- 2.我的解答 把问题分解为： 直径 = max{目前最大直径，左子树深度 + 右子树深度} /** * Definition for a binary tree node....right = travelTree(root->right, diameter); *diameter = max(*diameter, left + right); return 1
0 4 50 Sample Output Case 1: 100 Case 2: 80 这个题刚开始一直不理解，可能是对树的的直径比较陌生吧，可后来看看了看学长给我板子。...只要从任意一个节点出发然后找到距离他最远的节点，然后再让这个最远的出发去找距离这个最远的，这两个节点的距离就是树的直径！...从图中，你可以看到计算机4离1最远，所以s1=3。计算机4和5是距离2最远的，所以s2=2。计算机5是离3最远的，所以s3=3。我们也得到了s4=4，s5=4。...输入行中的数字用空格分隔。 输出 对于每组样例，输出n行。第i行第i台计算机的到其他计算机的最大长度Si（11最远，所以s1=3。计算机4和5是距离2最远的，所以s2=2。计算机5是离3最远的，所以s3=3。我们也得到了s4=4，s5=4。
Leetcode -404.左子叶之和 题目：给定二叉树的根节点 root ，返回所有左叶子之和。...示例 1： 输入: root = [3, 9, 20, null, null, 15, 7] 输出 : 24 解释 : 在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24 示例 2...root->right)) ans += sumOfLeftLeaves(root->right); return ans; } Leetcode -543.二叉树的直径...题目：给你一棵二叉树的根节点，返回该树的 直径 。...二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。 两节点之间路径的 长度 由它们之间边数表示。
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
ICP备案
云直播
对象存储
腾讯会议
