力扣(LeetCode)662

题目地址：

https://leetcode-cn.com/probl...

题目描述：

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

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

示例 1:

输入:

1
     /   \
    3     2
   / \     \  
  5   3     9

输出: 4

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

示例 2:

输入:

1
     /  
    3    
   / \       
  5   3

输出: 2

解释: 最大值出现在树的第 3 层，宽度为 2 (5,3)。

示例 3:

输入:

1
     / \
    3   2 
   /        
  5

输出: 2

解释: 最大值出现在树的第 2 层，宽度为 2 (3,2)。

示例 4:

输入:

1
     / \
    3   2
   /     \  
  5       9 
 /         \
6           7

输出: 8

解释: 最大值出现在树的第 4 层，宽度为 8 (6,null,null,null,null,null,null,7)。

解答：

这一题就是求每一层，最左边不为空的节点到最右边不为空的节点的距离。因此我们可以在层序遍历的时候

把空节点(这里的空节点指的是指的的一个特殊节点)也加入进去，这样对于每一层不空的节点，记录下标，然后找出最大最小值，就找到每一层的最大宽度。这样虽然思路没有问题，但是对于深度很深的树会超时。。。因为，这样做的话时间复杂度是指数级别(与树的深度成指数关系)。

java 超时代码：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int widthOfBinaryTree(TreeNode root) {
        if(root == null)return 0;
        int ans = 0;
        ArrayDeque<TreeNode> deque = new ArrayDeque(500);
        deque.offer(root);
        while(!deque.isEmpty())
        {
            int n = deque.size();
            int left = n,right = 0;
            for(int i = 0;i < n;i++)
            {
                TreeNode temp = deque.poll();
                if(temp.val != -9999)
                {
                  left = Math.min(left,i);
                  right = i;
                }
                
                
                if(temp.left != null)
                    deque.offer(temp.left);
                else deque.offer(new TreeNode(-9999));
                
                if(temp.right != null)
                    deque.offer(temp.right);
                else deque.offer(new TreeNode(-9999));
            }
            if(left == n&&right == 0)break;
            ans = Math.max(ans,right-left+1);
        }
        return ans;
    }
}

换一种思路，我们现在对这棵树进行深度优先遍历，但是遍历的时候记录下它是树的第几个节点,并且记录下它属于第几层，然后保存在hashmap中，map的键：层号，值：节点下标组成的列表，最后在访问hashmap找到每一层最大最小下标即找出答案。需要注意的是树的节点这样编号(如果root编号为1，那么它的左子树编号为2 i,右子树编号为2 i+1)。

java ac代码：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    HashMap<Integer,List<Integer>> map = new HashMap(5000);
    public int widthOfBinaryTree(TreeNode root) {
        if(root == null)return 0;
        int ans = 0;
        dfs(root,1,1);
        
        for(Map.Entry<Integer,List<Integer>> entry:map.entrySet() )
        {
            List<Integer> list= entry.getValue();
            int min = Integer.MAX_VALUE,max = Integer.MIN_VALUE;
            for(Integer i:list)
            {
                min = Math.min(min,i);
                max = Math.max(max,i);
            }
            ans = Math.max(ans,max-min+1);
        }
        
        return ans;
    }
    
    void dfs(TreeNode root,int i,int level)
    {
        if(root == null)return;
        if(map.get(level)==null)
        map.put(level,new ArrayList());
        map.get(level).add(i);
        dfs(root.left,2*i,level+1);
        dfs(root.right,2*i+1,level+1);
    }
    
}