LeetCode演算法題-Diameter of Binary Tree(Java實現)
這是悅樂書的第257 次更新,第270 篇原創
01 看題和準備
今天介紹的是LeetCode演算法題中Easy級別的第124題(順位題號是543)。給定二叉樹,您需要計算樹的直徑長度。 二叉樹的直徑是樹中任意兩個節點之間最長路徑的長度。 此路徑可能會也可能不會通過根節點。例:
給出一棵二叉樹
1 / \ 23 / \ 45
返回3,這是路徑[4,2,1,3]或[5,2,1,3]的長度。
注意:兩個節點之間的路徑長度由它們之間的邊數表示。
本次解題使用的開發工具是eclipse,jdk使用的版本是1.8,環境是win7 64位系統,使用Java語言編寫和測試。
02 解題
題目要求是求二叉樹的直徑,根據題目給的示例,也可以理解成從根節點開始,左子樹的深度與右子樹的深度之和,但是題目又說了,也可能不經過根節點,所以我們需要求兩者的最大值。計算任意一個節點的最長路徑值,在其中取出最大值即可。遞迴方法的主體,和求二叉樹最大深度的程式碼一樣,只是中間加了一步取最大值的操作而已。
此解法的時間複雜度是O(n),空間複雜度是O(n)。
public int diameterOfBinaryTree(TreeNode root) { helper(root); return max; } private int max = 0; public int helper(TreeNode root) { if (root == null) { return 0; } int left = helper(root.left); int right = helper(root.right); max = Math.max(max, left+right); return Math.max(left, right)+1; }
03 小結
演算法專題目前已日更超過三個月 ,演算法題文章124 +篇,公眾號對話方塊回覆【資料結構與演算法 】、【演算法 】、【資料結構 】中的任一關鍵詞,獲取系列文章合集。
以上就是全部內容,如果大家有什麼好的解法思路、建議或者其他問題,可以下方留言交流,點贊、留言、轉發就是對我最大的回報和支援!