优化网站加载速度,排名好的锦州网站建设,实时热搜榜榜单,滨海建设局官方网站文章目录 题目标题和出处难度题目描述要求示例数据范围 解法思路和算法代码复杂度分析 题目
标题和出处
标题#xff1a;二叉树的直径
出处#xff1a;543. 二叉树的直径
难度
3 级
题目描述
要求
给定二叉树的根结点 root \texttt{root} root#xff0c;返回其直径… 文章目录 题目标题和出处难度题目描述要求示例数据范围 解法思路和算法代码复杂度分析 题目
标题和出处
标题二叉树的直径
出处543. 二叉树的直径
难度
3 级
题目描述
要求
给定二叉树的根结点 root \texttt{root} root返回其直径长度。
二叉树的直径是任意两个结点之间的最长路径长度。这条路径可能穿过也可能不穿过根结点。
两个结点之间的路径长度由它们之间边的数目表示。
示例
示例 1 输入 root [1,2,3,4,5] \texttt{root [1,2,3,4,5]} root [1,2,3,4,5] 输出 3 \texttt{3} 3 解释 3 \texttt{3} 3 是路径 [4,2,1,3] \texttt{[4,2,1,3]} [4,2,1,3] 或 [5,2,1,3] \texttt{[5,2,1,3]} [5,2,1,3] 的长度。
示例 2
输入 root [1,2] \texttt{root [1,2]} root [1,2] 输出 1 \texttt{1} 1
数据范围
树中结点数目在范围 [1, 10 4 ] \texttt{[1, 10}^\texttt{4}\texttt{]} [1, 104] 内 -100 ≤ Node.val ≤ 100 \texttt{-100} \le \texttt{Node.val} \le \texttt{100} -100≤Node.val≤100
解法
思路和算法
二叉树中的任意一条路径一定经过某个子树的根结点子树可以是二叉树本身。
对于任意一个子树而言经过该子树根结点的最长路径以下称为「最长路径」均指包含根结点的最长路径一定满足以下条件如果左子树不为空则最长路径的左端是左子树的最深叶结点否则最长路径的左端是根结点如果右子树不为空则最长路径的右端是右子树的最深叶结点否则最长路径的右端是根结点。因此子树的最长路径长度为该子树的左子树和右子树的深度之和子树的深度为该子树的左子树和右子树的深度的较大值加 1 1 1。此处的深度定义为二叉树中结点的层数如果二叉树为空则深度为 0 0 0如果二叉树只有一个结点则深度为 1 1 1。
由于二叉树的最长路径长度和二叉树的深度都取决于左子树和右子树的深度因此可以使用深度优先搜索计算二叉树的深度计算过程中得到二叉树的直径。
计算二叉树的深度的过程是一个递归的过程递归的终止条件是当前结点为空此时深度为 0 0 0。其余情况下首先得到当前结点的左子树和右子树的深度然后计算以当前结点为根结点的二叉树的深度和最长路径长度并维护二叉树的直径。遍历结束之后即可得到二叉树的直径。
代码
class Solution {int diameter 0;public int diameterOfBinaryTree(TreeNode root) {getDepth(root);return diameter;}public int getDepth(TreeNode node) {if (node null) {return 0;}int leftDepth getDepth(node.left);int rightDepth getDepth(node.right);diameter Math.max(diameter, leftDepth rightDepth);return Math.max(leftDepth, rightDepth) 1;}
}复杂度分析 时间复杂度 O ( n ) O(n) O(n)其中 n n n 是二叉树的结点数。每个结点都被访问一次。 空间复杂度 O ( n ) O(n) O(n)其中 n n n 是二叉树的结点数。空间复杂度主要是递归调用的栈空间取决于二叉树的高度最坏情况下是 O ( n ) O(n) O(n)。
