内容简介:题目地址:题目描述:
题目地址:
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); } }
以上所述就是小编给大家介绍的《力扣(LeetCode)662》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
HTML 编码/解码
HTML 编码/解码
Markdown 在线编辑器
Markdown 在线编辑器