做网站前的准备工作,网站自己怎么做直播,备案成功后怎么建设网站,单位做网站支出应怎么核算题目描述
给你一棵二叉树的根节点#xff0c;返回该树的 直径 。
二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。
两节点之间路径的 长度 由它们之间边数表示。
示例 1#xff1a; 输入#xff1a;root [1,2,3,…题目描述
给你一棵二叉树的根节点返回该树的 直径 。
二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。
两节点之间路径的 长度 由它们之间边数表示。
示例 1 输入root [1,2,3,4,5]
输出3
解释3 取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。示例 2
输入root [1,2]
输出1提示
树中节点数目在范围 [1, 104] 内-100 Node.val 100
解答
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int diameter 0;int diameterOfBinaryTree(TreeNode* root) {// 左子树高 右子树高 直径// 直径在求树高过程中计算depth(root);return diameter;}int depth(TreeNode *root){if(root nullptr) return 0;int left depth(root-left);int right depth(root-right);// 最长路径也可能不经过根节点diameter max(diameter, left right);// 作为树高的计算return max(left, right) 1;}
};
