【二叉树】LeetCode 543. 二叉树的直径【简单】
2023-09-14 09:01:22 时间
给定一棵二叉树,你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
示例 :
给定二叉树
1 / \ 2 3 / \ 4 5
返回 3, 它的具体长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
注意:两结点之间的路径长度是以它们之间边的数目表示。
【分析】
使用递归,并且我们还需要找到合适的根节点。这是本题的特点。
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int: self.ans = 1 def depth(root): if not root: return 0 L = depth(root.left) R = depth(root.right) self.ans = max(self.ans, L+R+1) return max(L, R) + 1 depth(root) return self.ans - 1
相关文章
- Java实现 LeetCode 812 最大三角形面积 (暴力)
- Java实现 LeetCode 654 最大二叉树(递归)
- Java实现 LeetCode 637 二叉树的层平均值(遍历树)
- Java实现 LeetCode 559 N叉树的最大深度(遍历树,其实和便利二叉树一样,代码简短(●ˇ∀ˇ●))...
- Java实现 LeetCode 553 最优除法(思路问题)
- Java实现 LeetCode 526 优美的排列(DFS)
- Java实现 LeetCode 208 实现 Trie (前缀树)
- Java实现 LeetCode 110 平衡二叉树
- Java实现 LeetCode 103 二叉树的锯齿形层次遍历
- 【二叉树】LeetCode 101. 对称二叉树【简单】
- LeetCode(111):二叉树的最小深度
- 【二叉树】LeetCode 104. 二叉树的最大深度【简单】
- LeetCode-104. 二叉树的最大深度【DFS,BFS】
- ( “树” 之 DFS) 543. 二叉树的直径 ——【Leetcode每日一题】
- ( “树” 之 DFS) 104. 二叉树的最大深度 ——【Leetcode每日一题】
- Leetcode学习计划之动态规划入门day14(1314,120)
- 【LeetCode-面试算法经典-Java实现】【002-Add Two Numbers (单链表表示的两个数相加)】
- Leetcode 937. 重新排列日志文件(不容易,一次性过)
- Leetcode 263. 丑数
- 【LeetCode-面试算法经典-Java实现】【130-Surrounded Regions(围绕区域)】
- 【Leetcode刷题Python】110. 平衡二叉树
- 【Leetcode刷题Python】从列表list中创建一颗二叉树
- 【LeetCode】152.乘积最大子数组