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

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;//傳回節點深度
    }
}      

Result

複雜度分析

• 時間複雜度：O(N)

🌈尋寶

⭐今天是堅持刷題更文的第26/100天

⭐各位的點贊、關注、收藏、評論、訂閱就是一條創作的最大動力

⭐更多算法題歡迎關注專欄《leetcode》

為了回饋各位粉絲，禮尚往來，給大家準備了一條多年積累下來的優質資源，包括 學習視訊、面試資料、珍藏電子書等

怎麼領取請大家自己找，尋寶遊戲現在開始。

找不到可以評論留言，一條就會注意到你。

如果還不行，請私信我。