【Leetcode刷题篇】leetcode662 二叉树最大宽度

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

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

题解：用一个LinkedList数组来存储下标索引，对每层的索引相减即可得到最终值。

package com.lcz.leetcode;
/**
 * 二叉树的最大宽度
 * @author LvChaoZhang
 *
 */
import java.util.*;
public class Leetcode662 {
	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;
		}
	}
	// 直接修改
	public int widthOfBinaryTree(TreeNode root) {
		int width = 0;
		if(root==null) {
			return width;
		}
		// 层次遍历
		Deque<TreeNode> queue = new LinkedList<>();
		queue.offer(root);
		root.val = 0;

		while(!queue.isEmpty()) {
			int sum = queue.size();
			width = Math.max(width, queue.getLast().val-queue.getFirst().val+1);
			// 控制每层
			while(sum>0) {
				TreeNode p = queue.poll();
				
				if(p.left!=null) {
					p.left.val = p.val * 2 + 1;
					queue.offer(p.left);
					
				}
				
				if(p.right!=null) {
					p.right.val = p.val* 2 + 2;
					queue.offer(p.right);
				}
				sum--;
			}
			
		}
		
		return width;
	}
	
	
	 public int widthOfBinaryTree_2(TreeNode root) {
		 int width = 0;
		 if(root==null) {
			 return width;
		 }
		 
		 // 用队列来模拟
		 Queue<TreeNode> queue = new LinkedList<>();
		 queue.offer(root);
		// 存储序号
		 LinkedList<Integer> list = new LinkedList<>();
		 list.add(1);
		 int sum;
		 while(!queue.isEmpty()) {
			 sum  = queue.size();
			 width = Math.max(width, list.getLast()-list.getFirst()+1);
			 while(sum>0) {
				 TreeNode p = queue.poll();
				 Integer curIndex = list.removeFirst();
				 if(p.left!=null) {
					 queue.offer(p.left);
					 list.add(curIndex*2);
				 }
				 
				 if(p.right!=null) {
					 queue.offer(p.right);
					 list.add(curIndex*2+1);
				 }
				 sum--;
			 }
		 }
		 
		 return width;
		 
	 }
}