Go 刷 leetcode｜二叉樹的直徑

今天為大家講解 LeetCode 第 543 題，繼續(xù)為大家?guī)順涞念}目。

題目描述

給定一棵二叉樹，你需要計算它的直徑長度。一棵二叉樹的直徑長度是任意兩個結(jié)點路徑長度中的最大值。這條路徑可能穿過也可能不穿過根結(jié)點。

示例 : 給定二叉樹

      1
     / \
    2   3
   / \
  4   5

返回 3, 它的長度是路徑 [4,2,1,3] 或者 [5,2,1,3]。

注意：兩結(jié)點之間的路徑長度是以它們之間邊的數(shù)目表示。

來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/diameter-of-binary-tree 著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

解題思路

遍歷每一個節(jié)點，計算每個節(jié)點最大直徑（左子樹深度+右子樹深度），更新全局變量ans。

代碼實現(xiàn)

//go

//*?Definition?for?a?binary?tree?node.
type?TreeNode?struct?{
?Val?int
?Left?*TreeNode
?Right?*TreeNode
}

var?ans?=?0
func?diameterOfBinaryTree(root?*TreeNode)?int?{
?ans?=?0
?if?root?==?nil?{
??return?0
?}
?maxDepth(root)
?return?ans
}

//?節(jié)點node的最大深度
func?maxDepth(node?*TreeNode)?int?{
?if?node?==?nil?{
??return?0
?}
?lhight?:=?maxDepth(node.Left)
?rhight?:=?maxDepth(node.Right)
?ans?=?max(ans,?lhight+rhight)?//將每個節(jié)點最大直徑(左子樹深度+右子樹深度)當前最大值比較并取大者
?return?max(lhight,?rhight)+1??//返回節(jié)點深度
}

func?max(x?int,?y?int)?int?{
?if?x?>?y?{
??return?x
?}else?{
??return?y
?}
}

//java
class?Solution?{
????int?maxd=0;
????public?int?diameterOfBinaryTree(TreeNode?root)?{
????????depth(root);
????????return?maxd;
????}
????public?int?depth(TreeNode?node){
????????if(node==null){
????????????return?0;
????????}
????????int?Left?=?depth(node.left);
????????int?Right?=?depth(node.right);
????????maxd=Math.max(Left+Right,maxd);//將每個節(jié)點最大直徑(左子樹深度+右子樹深度)當前最大值比較并取大者
????????return?Math.max(Left,Right)+1;//返回節(jié)點深度
????}
}

鄭重聲明：

所展示代碼已通過 LeetCode 運行通過，請放心食用～