一条路径的长度为该路径经过的节点数减一，所以求直径等效于求路径经过的节点数的最大值减一。任意一条路径都可以看作由某个节点为起点，从其左子节点和右子节点向下遍历的路径拼接得到。假设我们知道对于某节点的左子节点向下遍历经过最多的节点数L和其右子节点向下遍历经过最多的节点数R，那么以该节点为起点的路径经过节点数的最大值即为L+R+1。
这个算法的时间复杂度是O（N），空间复杂度是O（N）。
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.ans = 1
def depth(node):
if not node:
return 0
L = depth(node.left)
R = depth(node.right)
self.ans = max(self.ans, L + R + 1)
return max(L, R) + 1
depth(root)
return self.ans - 1C++:
/**
* 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 {
int ans;
int depth(TreeNode* rt){
if (rt == NULL) {
return 0;
}
int L = depth(rt->left);
int R = depth(rt->right);
ans = max(ans, L + R + 1);
return max(L, R) + 1;
}
public:
int diameterOfBinaryTree(TreeNode* root) {
ans = 1;
depth(root);
return ans - 1;
}
};