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

示例 :
給定二叉樹

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

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

?

?

思路：利用遞歸，對每一個根節點，計算其左邊的深度和右邊的深度，左右深度相加即為當前子樹的直徑，遍歷完每一棵子樹后最大的那個直徑即為二叉樹的直徑。?

/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/ class Solution { public:int diameterOfBinaryTree(TreeNode* root) {int result = 0;if(root==NULL)return 0;core(root,result);return result;}int core(TreeNode* root, int& result){if(root==NULL)return 0;int depth_left = core(root->left,result);int depth_right = core(root->right,result);result = max(depth_left+depth_right,result);return max(depth_left+1,depth_right+1);} };

?

總結

以上是生活随笔為你收集整理的二叉树的直径—leetcode543的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。