题目描述

给定一个二叉树,编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与满二叉树(full binary tree)结构相同,但一些节点为空。

每一层的宽度被定义为两个端点(该层最左和最右的非空节点,两端点间的null节点也计入长度)之间的长度。

示例

输入: 

1
/ \
3 2
/ \ \
5 3 9

输出: 4
解释: 最大值出现在树的第 3 层,宽度为 4 (5,3,null,9)。

题目解析

  1. 层序遍历书中的每个节点,并给每个节点进行标号,标号规则如下
    1. root.val = 0
    2. root节点的左节点编号为2 * root.val,右节点的编号为2 * root.val + 1
  2. 当前层的宽度就是队列中最后一个节点的编号 - 第一个节点的编号 + 1
  3. 将当前root节点的左节点和右节点修改后入队列

Coding

/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int widthOfBinaryTree(TreeNode root) {
if(root == null){
return 0;
}
Deque<TreeNode> queue = new ArrayDeque<TreeNode>();
root.val = 0;
queue.offer(root);
int res = Integer.MIN_VALUE;
while(!queue.isEmpty()){
int n = queue.size();
res = Math.max(res,queue.getLast().val - queue.getFirst().val + 1);
System.out.println("left:" + queue.getLast().val + " right:" + queue.getFirst().val);
for(int i = 0;i < n;i++){
TreeNode node = queue.poll();
if(node.left != null){
node.left.val = 2 * node.val;
queue.offer(node.left);
}
if(node.right != null){
node.right.val = 2 * node.val + 1;
queue.offer(node.right);
}
}
}
return res;
}
}