原题
给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。
示例:
给定二叉树
1
/ \
2 3
/ \
4 5
返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
注意: 两结点之间的路径长度是以它们之间边的数目表示。
解法
思想
自底向上dfs，首先要了解这个最长边不一定经过根节点，对于每个结点，经过它的最长直径为左边的最长边和右边的最长边之和。这个结点的深度为左边最长边和右边最长边的最大值+1。这样获取出所有经过某节点的最长直径，比较出最大值。
代码
class Solution {
int max = 0;
public int diameterOfBinaryTree(TreeNode root) {
dfs(root);
return ans;
}
int dfs(TreeNode root){
if(root == null) return 0;
int left = dfs(root.left);
int right = dfs(root.right);
max = Math.max(max, left + right);
return Math.max(left, right) + 1;
}
}
原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode543-%e4%ba%8c%e5%8f%89%e6%a0%91%e7%9a%84%e7%9b%b4%e5%be%84/
相关推荐
-
leetcode498-对角线遍历
这是一个Z字形编排问题，JEPG的编码过程中也会用到。 原题 给定一个含有 M x N 个元素的矩阵（M 行，N 列），请以对角线遍历的顺序返回这个矩阵中的所有元素，对角线遍历如下...
-
leetcode85-最大矩形
原题 给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。 示例： 输入: [ ["1","0","1","0","0"...
-
leetcode119-杨辉三角II
原题 给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行。在杨辉三角中，每个数是它左上方和右上方的数的和。 示例: 输入: 3 输出: [1,3,3,1] 进阶： ...
-
leetcode1160-拼写单词
原题 给你一份『词汇表』（字符串数组） words 和一张『字母表』（字符串） chars。 假如你可以用 chars 中的『字母』（字符）拼写出 words 中的某个『单词』（字...
-
leetcode744-寻找比目标字母大的最小字母
原题 给定一个只包含小写字母的有序数组letters 和一个目标字母 target，寻找有序数组里面比目标字母大的最小字母。 数组里字母的顺序是循环的。举个例子，如果目标字母tar...
-
剑指offer17-打印从1到最大的n位数
原题（来源Leetcode） 输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。 示例 1: 输入： ...
-
leetcode160-相交链表
原题 编写一个程序，找到两个单链表相交的起始节点。 如下面的两个链表： 在节点 c1 开始相交。 示例 1： 输入： intersectVal = 8, listA = [4,1,...
-
leetcode443-压缩字符串
原题 给定一组字符，使用原地算法将其压缩。 压缩后的长度必须始终小于或等于原数组长度。 数组的每个元素应该是长度为1 的字符（不是 int 整数类型）。 在完成原地修改输入数组后，...
-
leetcode83-删除排序链表中的重复元素
今天打算多刷几道算法题 原题 给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。 示例 1: 输入: 1->1->2 输出: 1->2 示例 2: 输入: 1->1->...
-
leetcode125-验证回文串
原题 给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。 说明： 本题中，我们将空字符串定义为有效的回文串。 示例 1: 输入: "A man, a ...
