返回信息流[b]lz最近在做这题，这题的题意很明确，就是求一棵二叉树的最大宽度。但是这个宽度是指同一行中开头和结尾的两个节点之间的距离，包括空节点。
我的方法比较繁琐，首先求树高，然后按照树高，对每一层进行层次遍历，将每一层的值存入一个arraylist中，包括空值，其实就是存入了一棵完全二叉树，然后遍历完一层后，都计算下相应的这一层中的宽度，以此类推，直到每一层都遍历完，那么就得到了这棵二叉树的最大宽度。但是我写的代码在leetcode中运行，出现了超时的问题，求哪位大神帮lz看看代码，希望不要改变我的思路，谢谢！代码如下：
public class widthOfBinaryTree
{
public int widthOfBinaryTree(TreeNode root)
{
if(root == null)
return 0;
int height = getDepth(root);
Queue<TreeNode> queue = new LinkedList<>(); //队列用来对二叉树进行层次遍历
queue.add(root);
int max = 1;
for(int i = 0; i < height - 1; i++)
{
ArrayList<String> list = new ArrayList<>(); //对每一层的所有节点，包括空节点都保存进arraylist中，用于计算每一层的最大宽度
int curr = 0;
int length = queue.size();
for(int j = 0; j < length; j++)
{
TreeNode node = queue.poll();
if(node == null) //如果遇到此节点是空的，那么其左孩子和右孩子也必定是空的，那么就将相应的空节点保存进arraylist中
{
queue.add(null);
queue.add(null);
list.add(" ");
list.add(" ");
}
else if(node != null)
{
if(node.left != null)
{
queue.add(node.left);
list.add(String.valueOf(node.left.val));
}
else if(node.left == null)
{
queue.add(null);
list.add(" ");
}
if(node.right != null)
{
queue.add(node.right);
list.add(String.valueOf(node.right.val));
}
else if(node.right == null)
{
queue.add(null);
list.add(" ");
}
}
}
int start = 0;
int end = list.size() - 1;
while(start < end) //对一层遍历完后，来求其最大宽度，用start和end来限定
{
if(list.get(start) == " ")
{
start = start + 1;
}
if(list.get(end) == " ")
{
end = end - 1;
}
if(list.get(start) != " " && list.get(end) != " ")
break;
}
curr = end - start + 1;
max = max > curr ? max : curr;
}
return max;
}
public int getDepth(TreeNode root) //求树高
{
if(root == null)
return 0;
int left = getDepth(root.left);
int right = getDepth(root.right);
return 1 + Math.max(left,right);
}
}
这是一条镜像帖。来源：北邮人论坛 / acm-icpc / #93892同步于 2017/9/1
该镜像源已超过 30 天没有更新，可能在源站已被删除。
ACM_ICPC机器人发帖
LeetCode662 Maximum Width of Binary Tree
BILL
2017/9/1镜像同步28 回复
订阅后，新回复会通过你的通知中心匿名送达。
9 条回复
首先，你拿到层高的意义是什么？你既然是bfs了。一层一层的扫，当前层是什么高度，对你来说不重要的。所以你不需要先拿到depth，完全可以直接扫。其次，你为什么要保存中间的值？有什么意义么？你只是要的是当前节点在这一层的index而已。又不是要把整个树的值都过一遍。所以你的queue完全可以换成一个begin和一个end。然后就不需要再首尾去掉空字符这么麻烦了，还省去了入队，int换string，遍历队列的时间，而且你去掉首尾空字符的方法也很慢，用二分去找快点，你还要再来一个复杂度为o(n)的过滤方式。
在层序遍历的while里加一句
int curentWidth = queue.size();
然后for 1:currentWidth
queue.dequeue();
取currentWidth最大值即可
来自 缘邮
额，可是这个队列有保存空节点，如果只取最大的节点，并不能直接用于计算其最大宽度？不是特别明白你的思路，能再说得详细点吗？谢谢
【 在 xlrainy 的大作中提到: 】
: 在层序遍历的while里加一句
: int curentWidth = queue.size();
: 然后for 1:currentWidth
:
大神，感觉你说得很对，但还不是特别理解，能否直接在我上面的代码上改写新代码，谢谢！
【 在 NachtZ 的大作中提到: 】
: 首先，你拿到层高的意义是什么？你既然是bfs了。一层一层的扫，当前层是什么高度，对你来说不重要的。所以你不需要先拿到depth，完全可以直接扫。其次，你
你这，要我改你刷题有啥意义？你还不如去discuss区抄答案。
【 在 BILL 的大作中提到: 】
: 大神，感觉你说得很对，但还不是特别理解，能否直接在我上面的代码上改写新代码，谢谢！
哦 粗略看了下明白你的意思了 主要是当树形成单链表可能会超时吧，你这方法好像计算高度是有必要的。主要是在找start和end可以用二分查找去优化吧。
【 在 BILL 的大作中提到: 】
: 大神，感觉你说得很对，但还不是特别理解，能否直接在我上面的代码上改写新代码，谢谢！
按层遍历，每一层的每个节点包括所有null节点都放到一个arraylist里面，每层遍历完再处理一下，把arraylist里面的头尾的空节点去掉，记录arraylist最大值即可’
稍微改了下。。104/108 超过了内存限制，lz还是换种思路吧
public int widthOfBinaryTree(TreeNode root)
{
if(root == null)
return 0;
Queue<TreeNode> queue = new LinkedList<>(); //队列用来对二叉树进行层次遍历
queue.add(root);
int max = 1;
boolean flag = true;
while (!queue.isEmpty() && flag)
{
flag = false;
ArrayList<String> list = new ArrayList<>(); //对每一层的所有节点，包括空节点都保存进arraylist中，用于计算每一层的最大宽度
int curr = 0;
int length = queue.size();
for(int j = 0; j < length; j++)
{
TreeNode node = queue.poll();
if(node == null) //如果遇到此节点是空的，那么其左孩子和右孩子也必定是空的，那么就将相应的空节点保存进arraylist中
{
queue.add(null);
queue.add(null);
list.add(" ");
list.add(" ");
}
else if(node != null)
{
if(node.left != null)
{
queue.add(node.left);
list.add(String.valueOf(node.left.val));
flag = true;
}
else if(node.left == null)
{
queue.add(null);
list.add(" ");
}
if(node.right != null)
{
queue.add(node.right);
list.add(String.valueOf(node.right.val));
flag = true;
}
else if(node.right == null)
{
queue.add(null);
list.add(" ");
}
}
}
int start = 0;
int end = list.size() - 1;
while (start < end && list.get(start).equals(" ")) {
start++;
}
while (start < end && list.get(end).equals(" ")) {
end--;
}
// while(start < end) //对一层遍历完后，来求其最大宽度，用start和end来限定
// {
// if(list.get(start) == " ")
// {
// start = start + 1;
// }
// if(list.get(end) == " ")
// {
// end = end - 1;
// }
// if(list.get(start) != " " && list.get(end) != " ")
// break;
// }
curr = end - start + 1;
max = max > curr ? max : curr;
}
return max;
}
还有比较字符串最好用.equals()？