Re: [闲聊] 每日LeetCode

楼主: Rushia (みけねこ的鼻屎)   2023-04-21 01:02:31
662. Maximum Width of Binary Tree
给你一个二元树,找出他的最大宽度,最大宽度定义为每层的最左节点到最右节点
的距离。
Example:
https://assets.leetcode.com/uploads/2022/03/14/maximum-width-of-binary-tree-v3.jpg
Input: root = [1,3,2,5,3,null,9]
Output: 4
Explanation: The maximum width exists in the third level with length 4
(5,3,null,9).
https://assets.leetcode.com/uploads/2021/05/03/width3-tree.jpg
Input: root = [1,3,2,5,null,null,9,6,null,7]
Output: 7
Explanation: The maximum width exists in the fourth level with length 7
(6,null,null,null,null,null,7).
思路:
1.把这棵树当作一个完满二元树(Full BT)处理,每个节点都从左到右从上到下编号
,记录最左边的编号在一个 List(可用size来判断是否是最左node)
2.最长宽度为:MAX(左子树最长宽度, 右子树最长宽度, 当前节点和最左节点距离)
3.上面的关系式用用DFS去做处理就好,往左的话 id*2 往右 id*2 + 1。
Java Code:
作者: Che31128 (justjoke)   2023-04-21 01:04:00
大师

Links booklink

Contact Us: admin [ a t ] ucptt.com