app商城开发网站建设,月夜直播免费完整版观看,网站网页制作电话,餐饮连锁网站建设题目描述
给你一棵二叉树的根节点#xff0c;返回该树的 直径 。 二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。 两节点之间路径的 长度 由它们之间边数表示。
提示#xff1a;
树中节点数目在范围 [1, 10000] 内…题目描述
给你一棵二叉树的根节点返回该树的 直径 。 二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。 两节点之间路径的 长度 由它们之间边数表示。
提示
树中节点数目在范围 [1, 10000] 内
-100 Node.val 100题解
/*** Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/
int maxLen(struct TreeNode* root)
{if(root NULL){return 0; // Base case: return 0 if the current node is NULL}int leftLen;int rightLen;// Calculate the maximum path length of the left subtreeleftLen maxLen(root-left) 1;// Calculate the maximum path length of the right subtreerightLen maxLen(root-right) 1;// Return the maximum of the left and right path lengthsreturn leftLen rightLen ? leftLen : rightLen;
}int Traversal(struct TreeNode* root)
{if(root NULL){return INT_MIN; // Return minimum integer value if the current node is NULL}int diameter INT_MIN; // Initialize diameter to minimum integer value// Calculate the diameter passing through the current nodediameter maxLen(root-left) maxLen(root-right);// Update diameter with the maximum of diameter, left subtree traversal, and right subtree traversaldiameter fmax(diameter, Traversal(root-left));diameter fmax(diameter, Traversal(root-right));return diameter; // Return the final diameter value
}int diameterOfBinaryTree(struct TreeNode* root)
{// Post-order traversal to calculate the diameter of the binary treereturn Traversal(root);
}
