摘要:一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。注意两结点之间的路径长度是以它们之间边的数目表示。
题目地址:
https://leetcode-cn.com/probl...
题目描述:
给定一棵二叉树,你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。
示例 :
给定二叉树
1 / 2 3 / 4 5
返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
注意:两结点之间的路径长度是以它们之间边的数目表示。
解答:
这一题就是找到每个节点的深度(等于max(左节点深度,右节点深度)+1),因为穿过任意一个节点的
直径,为这个节点左子树的深度+右子树的深度。因此只需要计算出每个节点深度,就可以得到穿过
某节点的直径。因此得到深度之后可以选择利用dfs深度优先搜索来找到答案,也可以在求深度的时候
就直接计算,然后保存在hashmap中。
java ac代码:
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public int diameterOfBinaryTree(TreeNode root) { if(root == null)return 0; HashMapmap = new HashMap(500); height(root,map); int ans = 0; for(Map.Entry entry:map.entrySet()) ans = Math.max(ans,entry.getValue()); return ans; } public int height(TreeNode root,HashMap map) { if(root == null)return 0; int left = height(root.left,map); int right = height(root.right,map); int ans = left + right; map.put(root,ans); return Math.max(left,right)+1; } }
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/72914.html
Problem Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may ...
摘要:图因此可以成为树,在所有可能的树中,具有最小高度的树被称为最小高度树。给出这样的一个图,写出一个函数找到所有的最小高度树并返回他们的根节点。因此使用一个数组代表每个节点的入度,若入度为就是叶子节点。 题目地址:https://leetcode-cn.com/probl...题目描述: 对于一个具有树特征的无向图,我们可选择任何一个节点作为根。图因此可以成为树,在所有可能的树中,具有最小...
摘要:关于递归这里提一两点递归基本有这几步递归的模板,终止条件,递归调用,逻辑处理。 ?作者简介:大家好,我是车神哥,府学路18号的车神? ?个人主页:应无所住而生...
摘要:对于每个气球,提供的输入是水平方向上,气球直径的开始和结束坐标。可以射出的弓箭的数量没有限制。弓箭一旦被射出之后,可以无限地前进。我们想找到使得所有气球全部被引爆,所需的弓箭的最小数量。解答这是一道区间覆盖问题,不太好说清楚,利用模板即可。 题目地址:https://leetcode-cn.com/probl...题目描述:在二维空间中有许多球形的气球。对于每个气球,提供的输入是水平方...
阅读 1106·2021-11-23 10:05
阅读 1784·2021-11-12 10:36
阅读 1853·2019-08-30 15:56
阅读 1684·2019-08-29 12:32
阅读 3042·2019-08-28 18:04
阅读 3427·2019-08-26 12:17
阅读 2502·2019-08-26 11:35
阅读 1240·2019-08-23 15:11