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