二叉树的最大宽度

[编程题]二叉树的最大宽度

热度指数：2734 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个二叉树，请你求出此二叉树的最大宽度。

本题中树第 i 层的宽度定义为：第 i 层最左边的节点到最右边之间的距离，中间空节点也计入距离。

例如：

本树中第 1 层只有一个节点，故第 1 层宽度是 1 ，第二层最左侧到最右侧的距离是 2 ，所以宽度是 2 ，第三层最左侧 4 到最右侧 5 距离是 4 ，故宽度是 4，此树最大宽度是 4。

示例1

输入

{1,2,3,4,#,4,5}

输出

说明

如题面图

示例2

输入

{1}

输出

示例3

输入

{1,2,3,4,#,4,5,6,#,1}

输出

说明

倒数第二层的宽度为5

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

算法知识视频讲解

Javascript

nicole27

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;
}

发表于 2022-03-25 15:42:41 回复(0)