题目地址：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，那么它的左子树编号为2i,右子树编号为2i+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,2i,level+1); dfs(root.right,2*i+1,level+1); } }