class Solution {
public:
//递归函数的返回值定义为从当前结点到叶子结点的最大长度
int dfs(TreeNode* node, int &ans)
{
if (!node) return 0;
int d1 = dfs(node->left, ans);
int d2 = dfs(node->right, ans);
ans = max(ans, d1 + d2);
return max(d1, d2) + 1;
}
int diameterOfBinaryTree(TreeNode* root) {
int ans = 0;
dfs(root, ans);
return ans;
}
};
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 = 0
self.dfs(root)
return self.res
def dfs(self, root):
if root is None: return 0
d1 = self.dfs(root.left)
d2 = self.dfs(root.right)
self.res = max(d1+d2, self.res)
return max(d1,d2)+1