专业的电商网站建设公司,网络营销乐云seo,跨平台软件开发工具,微模板网站建设目录 题目描述#xff1a;543. 二叉树的直径#xff08;简单#xff09;题目接口解题思路代码 PS: 题目描述#xff1a;543. 二叉树的直径#xff08;简单#xff09;
给你一棵二叉树的根节点#xff0c;返回该树的 直径 。
二叉树的 直径 是指树中任意两个节点之间最… 目录 题目描述543. 二叉树的直径简单题目接口解题思路代码 PS: 题目描述543. 二叉树的直径简单
给你一棵二叉树的根节点返回该树的 直径 。
二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。
两节点之间路径的 长度 由它们之间边数表示。
LeetCode做题链接LeetCode-两数之和
示例 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.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val val;* this.left left;* this.right right;* }* }*/
class Solution {public int diameterOfBinaryTree(TreeNode root) {}
}解题思路
递归 定义一个全局变量ans用来存储计算过程中的最大直径。 定义一个方法diameterOfBinaryTree(TreeNode root)这个方法是求解二叉树直径的主方法。如果传入的根节点为空那么直接返回0表示没有节点直径为0。否则调用maxDepth(root)方法求出以当前节点为根的子树的最大深度然后用这个深度减去1因为直径需要经过根节点得到左子树和右子树的最大深度之和再减去2因为直径需要经过两个子节点就得到了以当前节点为根的子树的直径。最后用全局变量ans更新最大直径。 定义一个方法maxDepth(TreeNode root)这个方法是递归求解以当前节点为根的子树的最大深度。如果传入的根节点为空那么直接返回0表示没有节点深度为0。否则递归求解左子树和右子树的最大深度然后取两者中的较大值加1作为当前节点的深度。同时用这个深度更新全局变量ans。 在主方法中首先检查根节点是否为空如果为空则直接返回0。然后调用maxDepth(root)方法求出以当前节点为根的子树的最大深度并用这个深度更新全局变量ans。最后返回ans即为整棵树的直径。
代码
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val val;* this.left left;* this.right right;* }* }*/
class Solution {// 定义一个全局变量用来存储计算过程中的最大直径private int ans;// 主方法求解二叉树的直径public int diameterOfBinaryTree(TreeNode root) {// 如果根节点为空返回0if(root null){return 0;}// 求以当前节点为根的子树的最大深度maxDepth(root);// 返回最大直径return ans;}// 递归方法求以当前节点为根的子树的最大深度public int maxDepth(TreeNode root) {// 如果根节点为空返回0if(root null){return 0;}// 递归求解左子树和右子树的最大深度然后取两者中的较大值加1作为当前节点的深度int left maxDepth(root.left) 1;int right maxDepth(root.right) 1;// 用当前节点的深度更新全局变量ansans Math.max(ans, left right - 2);// 返回当前节点的深度return Math.max(left, right);}
}成功
PS:
感谢您的阅读如果您觉得本篇文章对您有所帮助请给予博主一个赞喔~
