題目
給定一棵二叉樹靖诗，你需要計(jì)算它的直徑長(zhǎng)度蓖墅。一棵二叉樹的直徑長(zhǎng)度是任意兩個(gè)結(jié)點(diǎn)路徑長(zhǎng)度中的最大值。這條路徑可能穿過也可能不穿過根結(jié)點(diǎn)藕帜。
LeetCode543.二叉樹的直徑
解析
遞歸實(shí)現(xiàn)意乓。每個(gè)節(jié)點(diǎn)穿過自己的最長(zhǎng)直徑是其左右子樹的樹高和（葉子節(jié)點(diǎn)樹高為1）樱调，比較當(dāng)前記錄的最長(zhǎng)直徑，進(jìn)行更新届良。遞歸函數(shù)返回給上一層的值是節(jié)點(diǎn)左右子樹樹高比較后的最大值加1笆凌。
代碼
class Solution {
//這條路徑可能穿過也可能不穿過根結(jié)點(diǎn)。
//記錄的遞歸到的最大直徑
int result = -1;
public int diameterOfBinaryTree(TreeNode root) {
if(null == root){
return 0;
}
maxPath(root);
return result;
}
//遞歸函數(shù)
private int maxPath(TreeNode node){
if(null == node){
return 0;
}
int lp = maxPath(node.left);
int rp = maxPath(node.right);
//每個(gè)節(jié)點(diǎn)穿過自己的最長(zhǎng)直徑是其左右子樹的樹高和（葉子節(jié)點(diǎn)樹高為1）
//比較當(dāng)前記錄的最長(zhǎng)直徑士葫，進(jìn)行更新
result = (lp + rp) > result ? (lp + rp) : result;
//返回節(jié)點(diǎn)左右子樹樹高比較后的最大值加1
return lp > rp ? lp + 1 : rp + 1;
}
}
