543. 二叉樹(shù)的直徑

Ideas

這題貌似也在左神算法里見(jiàn)過(guò)。

基本思想就是遞歸，根節(jié)點(diǎn)從左子樹(shù)獲得一個(gè)想要的信息，從右子樹(shù)獲得一個(gè)想要的信息，然后對(duì)兩個(gè)信息進(jìn)行處理。

其實(shí)可以把直徑分成兩半看：從根節(jié)點(diǎn)到左子樹(shù)的葉子結(jié)點(diǎn)的最長(zhǎng)路徑+根節(jié)點(diǎn)到右子樹(shù)的葉子結(jié)點(diǎn)的最長(zhǎng)路徑-1。

然后就簡(jiǎn)單了，問(wèn)題就轉(zhuǎn)變成了求二叉樹(shù)的深度。

Code

C++

class Solution {int ans = 1;int depth(TreeNode* rt) {if (rt == NULL) {return 0;}int l_depth = depth(rt->left);int r_depth = depth(rt->right);ans = max(ans, l_depth + r_depth + 1);return max(l_depth, r_depth) + 1;} public:int diameterOfBinaryTree(TreeNode* root) {depth(root);return ans - 1;} };

總結(jié)

以上是生活随笔為你收集整理的LeetCode Algorithm 543. 二叉树的直径的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。