给你一棵二叉树的根节点,返回该树的 直径 。
二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。
两节点之间路径的 长度 由它们之间边数表示。
输入:root = [1,2,3,4,5]
输出:3
解释:3 ,取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。
> 代码
class Solution {
public:
//二叉树的最长路径=max{左子树的最长路径,右子树的最长路径,左子树的深度+右子树的深度}
int traverse(TreeNode* root, int& diameter) {
if (root == nullptr) {
return 0;
}
int left = traverse(root->left, diameter);
int right = traverse(root->right, diameter);
diameter = max(diameter, left + right);
return 1 + max(left, right);
}
int diameterOfBinaryTree(TreeNode* root) {
int diameter = 0;
traverse(root, diameter);
return diameter;
}
};
标签:diameter,traverse,int,路径,543,二叉树,直径,root
From: https://www.cnblogs.com/lihaoxiang/p/17711637.html