题解 | #二叉树的最大宽度#

先获取树的最大深度，然后按照深度把原树改为一棵完全二叉树，添加上去的节点是一个特殊值的标记节点，然后再进行层序遍历获取每一层的节点值，再对每一层的节点进行获取，把最左边和最右边的是特殊值的树节点去掉，最终得到的就是该层的实际宽度，然后遍历得到最大宽度即可。 import java.util.*;

/*

• public class TreeNode {
• int val = 0;
• TreeNode left = null;
• TreeNode right = null;
• public TreeNode(int val) {

• this.val = val;
  

• }
• } */

public class Solution {

int temp = Integer.MAX_VALUE;//特殊值
int depth =0; //树的最大深度
public int widthOfBinaryTree (TreeNode root) {
    // write code here
    int maxWide=0;
    //获取树的最大深度
    depth = maxDepth(root);
    //把树填成一个完全二叉树
    fillTree(root,1);
    ArrayList<ArrayList<Integer>> res = new ArrayList<>();
    //层序遍历获取最大宽度，在这个过程中不要去计算最左边或最右边的特殊值的节点
    levelOfIteratorTree(root,res,0);
    for (ArrayList<Integer> list : res) {
        int length = list.size();
        for (Integer integer : list) {
            if (integer == Integer.MAX_VALUE) {
                length--;
            } else {
                break;
            }
        }
        for (int size = list.size()-1; size >= 0; size--) {
            if(list.get(size)==Integer.MAX_VALUE){
                length--;
            } else {
                break;
            }
        }
        maxWide=Math.max(maxWide,length);
    }
    return maxWide;
}

private void levelOfIteratorTree(TreeNode root, ArrayList<ArrayList<Integer>> res, int level) {
    if(level==res.size()){
        res.add(new ArrayList<>());
    }
    res.get(level).add(root.val);
    if(root.left!=null){
        levelOfIteratorTree(root.left,res,level+1);
    }
    if(root.right!=null){
        levelOfIteratorTree(root.right,res,level+1);
    }
}

private void fillTree(TreeNode root,int curDepth) {
    if(root==null){
        return;
    }
    if(root.right == null&&root.left == null&&curDepth<=depth){
        root.right=new TreeNode(temp);
        root.left=new TreeNode(temp);
    } else
    if(root.left == null&&curDepth<=depth){
        root.left=new TreeNode(temp);
    } else
    if(root.right == null&&curDepth<=depth){
        root.right=new TreeNode(temp);
    }
    fillTree(root.left,curDepth+1);
    fillTree(root.right,curDepth+1);

}

public int maxDepth (TreeNode root) {
    if(root == null){
        return 0;
    }
    int max = 0;
    if(root.left!=null){
        max = Math.max(max,maxDepth(root.left));
    }
    if(root.right!=null){
        max = Math.max(max,maxDepth(root.right));
    }
    return max+1;
}

}