題目描述
給定一棵二叉樹撒妈，你需要計算它的直徑長度指孤。一棵二叉樹的直徑長度是任意兩個結點路徑長度中的最大值孵班。這條路徑可能穿過根結點绝葡。
示例 :
給定二叉樹
1
/ \
2 3
/ \
4 5
返回 3, 它的長度是路徑 [4,2,1,3] 或者 [5,2,1,3]鄙漏。
注意：兩結點之間的路徑長度是以它們之間邊的數(shù)目表示嗤谚。
解題思路
利用遞歸的思路，從根節(jié)點開始怔蚌，計算每個節(jié)點的高度：等于左右孩子節(jié)點的高度的最大值加1巩步。
任意一條路徑可以被寫成兩個 箭頭（不同方向），每個箭頭代表一條從某些點向下遍歷到孩子節(jié)點的路徑桦踊。
假設我們知道對于每個節(jié)點最長箭頭距離分別為 L, R椅野，那么最優(yōu)路徑經過 L + R + 1 個節(jié)點。
算法
按照常用方法計算一個節(jié)點的深度：max(depth of node.left, depth of node.right) + 1籍胯。在計算的同時竟闪，經過這個節(jié)點的路徑長度為 1 + (depth of node.left) + (depth of node.right) 。搜索每個節(jié)點并記錄這些路徑經過的點數(shù)最大值杖狼，期望長度是結果 - 1炼蛤。
代碼實現(xiàn)
// C++版本
/**
* 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 maxDepth(TreeNode* node, int& ans) {
if (node == nullptr) return 0;
int L = maxDepth(node->left, ans);
int R = maxDepth(node->right, ans);
ans = max(ans, L+R+1);
return max(L, R)+1;
}
int diameterOfBinaryTree(TreeNode* root) {
int ans = 1;
maxDepth(root, ans);
return ans-1;
}
};
# python版本
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def diameterOfBinaryTree(self, root: TreeNode) -> int:
self.res = 1
def maxDepth(node):
if node == None:
return 0
L = maxDepth(node.left)
R = maxDepth(node.right)
self.res = max(self.res, L+R+1)
return max(L, R) + 1
maxDepth(root)
return self.res - 1
