【leetcode刷題】27.二叉樹的直徑—

?歡迎訂閱《leetcode》專欄，每日一題，每天進步?

可以將二叉樹的直徑轉換為：二叉樹的每個節點的左右子樹的高度和的最大值，

——leetcode此題熱評

前言

哈嘍，大家好，我是一條，

糊涂演算法，難得糊涂

Question

543. 二叉樹的直徑

難度：簡單

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

示例 :

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

注意：兩結點之間的路徑長度是以它們之間邊的數目表示，

Solution

還是遞回+深度優先搜索

我們定義一個遞回函式 depth(node) ，函式回傳該節點為根的子樹的深度，先遞回呼叫左兒子和右兒子求得它們為根的子樹的深度 L和 R，則該節點為根的子樹的深度即為max(L,R)+1

遞回搜索每個節點回傳最大值即可，

Code

所有leetcode代碼已同步至github

歡迎star

/**
 * @author yitiaoIT
 */
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);//將每個節點最大直徑(左子樹深度+右子樹深度)當前最大值比較并取大者
        return Math.max(Left,Right)+1;//回傳節點深度
    }
}