資訊專欄INFORMATION COLUMN
摘要：一棵二叉樹的直徑長度是任意兩個(gè)結(jié)點(diǎn)路徑長度中的最大值。這條路徑可能穿過根結(jié)點(diǎn)。注意兩結(jié)點(diǎn)之間的路徑長度是以它們之間邊的數(shù)目表示。
題目地址：
https://leetcode-cn.com/probl...
題目描述：
給定一棵二叉樹，你需要計(jì)算它的直徑長度。一棵二叉樹的直徑長度是任意兩個(gè)結(jié)點(diǎn)路徑長度中的最大值。這條路徑可能穿過根結(jié)點(diǎn)。
示例 :
給定二叉樹
1
/
2 3
/
4 5
返回 3, 它的長度是路徑 [4,2,1,3] 或者 [5,2,1,3]。
注意：兩結(jié)點(diǎn)之間的路徑長度是以它們之間邊的數(shù)目表示。
解答：
這一題就是找到每個(gè)節(jié)點(diǎn)的深度(等于max(左節(jié)點(diǎn)深度,右節(jié)點(diǎn)深度)+1)，因?yàn)榇┻^任意一個(gè)節(jié)點(diǎn)的
直徑，為這個(gè)節(jié)點(diǎn)左子樹的深度+右子樹的深度。因此只需要計(jì)算出每個(gè)節(jié)點(diǎn)深度，就可以得到穿過
某節(jié)點(diǎn)的直徑。因此得到深度之后可以選擇利用dfs深度優(yōu)先搜索來找到答案，也可以在求深度的時(shí)候
就直接計(jì)算，然后保存在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;
HashMap map = 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,HashMapmap)
{
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;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.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 ...
摘要：圖因此可以成為樹，在所有可能的樹中，具有最小高度的樹被稱為最小高度樹。給出這樣的一個(gè)圖，寫出一個(gè)函數(shù)找到所有的最小高度樹并返回他們的根節(jié)點(diǎn)。因此使用一個(gè)數(shù)組代表每個(gè)節(jié)點(diǎn)的入度，若入度為就是葉子節(jié)點(diǎn)。 題目地址：https://leetcode-cn.com/probl...題目描述： 對(duì)于一個(gè)具有樹特征的無向圖，我們可選擇任何一個(gè)節(jié)點(diǎn)作為根。圖因此可以成為樹，在所有可能的樹中，具有最小...
摘要：關(guān)于遞歸這里提一兩點(diǎn)遞歸基本有這幾步遞歸的模板，終止條件，遞歸調(diào)用，邏輯處理。 ?作者簡介：大家好，我是車神哥，府學(xué)路18號(hào)的車神? ?個(gè)人主頁：應(yīng)無所住而生...
摘要：對(duì)于每個(gè)氣球，提供的輸入是水平方向上，氣球直徑的開始和結(jié)束坐標(biāo)?？梢陨涑龅墓臄?shù)量沒有限制。弓箭一旦被射出之后，可以無限地前進(jìn)。我們想找到使得所有氣球全部被引爆，所需的弓箭的最小數(shù)量。解答這是一道區(qū)間覆蓋問題，不太好說清楚，利用模板即可。 題目地址：https://leetcode-cn.com/probl...題目描述：在二維空間中有許多球形的氣球。對(duì)于每個(gè)氣球，提供的輸入是水平方...
閱讀 1255·2021-11-23 10:05
閱讀 1902·2021-11-12 10:36
閱讀 1919·2019-08-30 15:56
閱讀 1751·2019-08-29 12:32
閱讀 3109·2019-08-28 18:04
閱讀 3486·2019-08-26 12:17
閱讀 2555·2019-08-26 11:35
閱讀 1315·2019-08-23 15:11
