力扣(LeetCode)662

栏目: 数据库 · 发布时间: 5年前

内容简介:题目地址:题目描述:

题目地址:

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》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Java与模式

Java与模式

阎宏 编著 / 电子工业出版社 / 2002-10 / 88.00元

《Java与模式》是一本讲解设计原则以及最为常见的设计模式的实用教材,目的是为了工作繁忙的Java系统设计师提供一个快速而准确的设计原则和设计模式的辅导。全书分为55章,第一个章节讲解一个编编程模式,说明此模式的用意、结构,以及这一模式适合于什么样的情况等。每一个章节都附有多个例子和练习题,研习这些例子、完成这些练习题可以帮助读者更好地理解所讲的内容。大多数的章节都是相对独立的,读者可以从任何一章......一起来看看 《Java与模式》 这本书的介绍吧!

HTML 编码/解码
HTML 编码/解码

HTML 编码/解码

Markdown 在线编辑器
Markdown 在线编辑器

Markdown 在线编辑器