Re: [閒聊] 每日LeetCode已回收
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：
-------------------------------------------------------
class Solution {
public int widthOfBinaryTree(TreeNode root) {
if (root == null) return 0;
return dfs(root, 0, 1, new ArrayList<>());
}
private int dfs(TreeNode root, int level, int id, List<Integer>
startNodes) {
if (root == null) return 0;
if (startNodes.size() == level) {
startNodes.add(id);
}
int left = dfs(root.left, level + 1, id * 2, startNodes);
int right = dfs(root.right, level + 1, id * 2 + 1, startNodes);
return Math.max(id - startNodes.get(level) + 1, Math.max(left,
right));
}
}
-------------------------------------------------------
--
https://i.imgur.com/bFRiqA3.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.75.86 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1682010154.A.A1B.html
推
04/21 01:04,
2年前
, 1F
04/21 01:04, 1F
討論串 (同標題文章)
完整討論串 (本文為第 299 之 719 篇)：