做网站用哪个工具,上海集团登录入口,商务网站建设考试题库,医疗协助平台网站建设方案原题链接#x1f517;#xff1a;二叉树的直径 难度#xff1a;简单⭐️
题目
给你一棵二叉树的根节点#xff0c;返回该树的 直径 。
二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。
两节点之间路径的 长度 由…原题链接二叉树的直径 难度简单⭐️
题目
给你一棵二叉树的根节点返回该树的 直径 。
二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 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
二叉树直径 二叉树的直径通常指的是二叉树中任意两个节点间的最长路径的长度。这个路径不一定经过根节点。二叉树的直径可以通过以下步骤求解 计算高度首先需要计算二叉树的高度。这可以通过递归函数实现递归地计算左子树和右子树的高度并返回两者中较大的一个加上当前节点的高度。 更新直径在计算高度的同时可以更新直径。对于每个节点其左子树的高度加上其右子树的高度就是通过该节点的路径长度这个长度可能是当前的直径。 返回结果最终返回记录的最大直径值。 题解
递归法
解题思路 理解问题首先明确题目要求的“直径”是指二叉树中任意两个节点之间的最长路径长度。这个路径可以不经过根节点。 递归计算高度二叉树的高度可以通过递归计算得到。对于每个节点其高度是其左子树和右子树高度的最大值加1。 同时更新直径在计算高度的过程中可以同时更新直径。对于每个节点其左子树的高度加上其右子树的高度就是通过该节点的一条可能的最长路径长度。这个长度可能是当前的直径。 使用辅助变量由于直径的计算依赖于递归过程中的信息因此可以使用一个辅助变量来存储遍历过程中发现的最长路径长度。 遍历结束当递归遍历完整棵树后辅助变量中存储的就是二叉树的直径。 注意边界条件在递归函数中如果当前节点为空应该返回0因为空树的高度是0。 返回结果最终返回辅助变量中的值作为二叉树的直径。 复杂度 时间复杂度O(N)其中 N 为二叉树的节点数即遍历一棵二叉树的时间复杂度每个结点只被访问一次。空间复杂度O(Height)其中 Height 为二叉树的高度。由于递归函数在递归过程中需要为每一层递归函数分配栈空间所以这里需要额外的空间且该空间取决于递归的深度而递归的深度显然为二叉树的高度并且每次递归调用的函数里又只用了常数个变量所以所需空间复杂度为 O(Height)。 c demo
#include iostream
#include algorithm
#include climits
#include queue// 定义二叉树的节点结构
struct TreeNode {int val;TreeNode* left;TreeNode* right;TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};// 解决方案类
class Solution {
public:// 计算二叉树的直径int diameterOfBinaryTree(TreeNode* root) {this-maxDiameter 0; // 初始化最大直径为0calculateHeight(root); // 计算树的高度并更新最大直径return maxDiameter;}private:int maxDiameter; // 用于存储最大直径// 计算以node为根的二叉树的高度并更新最大直径int calculateHeight(TreeNode* node) {if (!node) return 0; // 如果节点为空返回高度0// 计算左子树和右子树的高度int leftHeight calculateHeight(node-left);int rightHeight calculateHeight(node-right);// 更新最大直径如果通过当前节点的路径更长maxDiameter std::max(maxDiameter, leftHeight rightHeight);// 返回当前节点的高度即左右子树高度的最大值加1return std::max(leftHeight, rightHeight) 1;}
};// 主函数用于测试算法
int main() {// 创建一个示例二叉树// 1// / \// 2 3// / \// 4 5TreeNode* root new TreeNode(1);root-left new TreeNode(2);root-right new TreeNode(3);root-left-left new TreeNode(4);root-left-right new TreeNode(5);// 创建解决方案实例Solution solution;// 计算并输出二叉树的直径std::cout The diameter of the binary tree is: solution.diameterOfBinaryTree(root) std::endl;// 清理分配的内存在实际应用中应该使用智能指针来避免内存泄漏delete root-left-left;delete root-left-right;delete root-left;delete root-right;delete root;return 0;
}输出结果 The diameter of the binary tree is: 3
