给定一个二叉树,请你求出此二叉树的最大宽度。
本题中树第 i 层的宽度定义为:第 i 层最左边的节点到最右边之间的距离,中间空节点也计入距离。
例如:
本树中第 1 层只有一个节点,故第 1 层宽度是 1 ,第二层最左侧到最右侧的距离是 2 ,所以宽度是 2 , 第三层最左侧 4 到最右侧 5 距离是 4 ,故宽度是 4,此树最大宽度是 4。
{1,2,3,4,#,4,5}
4
如题面图
{1}
1
{1,2,3,4,#,4,5,6,#,1}
5
倒数第二层的宽度为5
function widthOfBinaryTree( root ) { // write code here const queue = [[root, 0]]; let res = 0; // 全局维护最大值 let left = 0; // 记录当前层最左边节点的计数值 let right = 0; // 记录当前层最右边节点的计数值 while (queue.length) { left = queue[0][1]; const len = queue.length; for (let i = 0; i < len; i++) { let [h, pos] = queue.shift(); right = pos; if (h.left) queue.push([h.left, 2 * (pos - left)]); // 重点,优化掉左边不需要计数的部分 if (h.right) queue.push([h.right, 2 * (pos - left) + 1]); } res = Math.max(res, right - left + 1); } return res; }