精华内容
下载资源
问答
  • 二叉树最大宽度

    千次阅读 2019-09-20 14:15:35
    二叉树最大宽度 题目 给定一个二叉树,编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与满二叉树(full binary tree)结构相同,但一些节点为空。 每一层的宽度被定义为两个端点...

    二叉树最大宽度

    题目

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

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

    解题

    思路

    一个二叉树,从根节点开始,从0开始,一次往后编码,1、2、3、4…

    这样每一个根节点i的左子节点都是2 * i + 1;右子节点都是2 * i + 2;

    再利用队列进行bfs,每一行的最大值减去最小值加一就是这个二叉树的最大宽度。

    时间复杂度为O(n),空间复杂度也是O(n)。

    代码

    class Solution {
        public int widthOfBinaryTree(TreeNode root) {
    
            if (root == null) {
                return 0;
            }
            
            LinkedList<TreeNode> queue = new LinkedList<>();
            root.val = 0;
            queue.add(root);
    
            int result = 0;
            while (!queue.isEmpty()) {
                if (queue.getLast().val - queue.getFirst().val + 1 > result) {
                    result = queue.getLast().val - queue.getFirst().val + 1;
                }
                int size = queue.size();
                for (int i = 0; i < size; i++) {
                    TreeNode temp = queue.poll();
                    if (temp.left != null) {
                        temp.left.val = temp.val * 2 + 1;
                        queue.add(temp.left);
                    }
                    if (temp.right != null) {
                        temp.right.val = temp.val * 2 + 2;
                        queue.add(temp.right);
                    }
                }
            }
    
            return result;
        }
    }
    
    展开全文
  • 二叉树最大宽度 数据结构 求二叉树最大宽度 数据结构
  • import java.util.HashMap;import java.util..../*** 二叉树最大宽度*/public class TreeMaxWidth {/*** 不使用HashMap实现** @param head 二叉树的头节点* @return 最大宽度*/public int treeMaxWidthNoMap...

    import java.util.HashMap;

    import java.util.LinkedList;

    import java.util.Queue;

    /**

    * 二叉树最大宽度

    */

    public class TreeMaxWidth {

    /**

    * 不使用HashMap实现

    *

    * @param head 二叉树的头节点

    * @return 最大宽度

    */

    public int treeMaxWidthNoMap(Node head) {

    int maxWidth = 0;

    if (head == null) {

    return maxWidth;

    }

    // 用队列实现

    Queue queue = new LinkedList<>();

    queue.add(head);

    Node curEnd = head;

    Node nextEnd = null;

    int curWidth = 0;

    while (!queue.isEmpty()) {

    Node node = queue.poll();

    if (node.left != null) {

    queue.add(node.left);

    nextEnd = node.left;

    }

    if (node.right != null) {

    queue.add(node.right);

    nextEnd = node.right;

    }

    curWidth++;

    if (node == curEnd) {

    maxWidth = Math.max(maxWidth, curWidth);

    curWidth = 0;

    curEnd = nextEnd;

    }

    }

    return maxWidth;

    }

    /**

    * 使用HashMap实现

    *

    * @param head 二叉树的头节点

    * @return 最大宽度

    */

    public int treeMaxWidthUseMap(Node head) {

    int maxWidth = 0;

    if (head == null) {

    return maxWidth;

    }

    // 用队列实现

    Queue queue = new LinkedList<>();

    queue.add(head);

    // 节点对应在哪一层

    HashMap levelMap = new HashMap<>();

    levelMap.put(head, 1);

    int curWidth = 0;

    int level = 1;

    while (!queue.isEmpty()) {

    Node node = queue.poll();

    int curLevel = levelMap.get(node);

    if (node.left != null) {

    queue.add(node.left);

    levelMap.put(node.left, levelMap.get(node) + 1);

    }

    if (node.right != null) {

    queue.add(node.right);

    levelMap.put(node.right, levelMap.get(node) + 1);

    }

    if (curLevel == level) {

    curWidth++;

    } else {

    maxWidth = Math.max(maxWidth, curWidth);

    level = curLevel;

    curWidth = 1;

    }

    }

    maxWidth = Math.max(maxWidth, curWidth);

    return maxWidth;

    }

    /**

    * 二叉树结构

    */

    public static class Node {

    public int value;

    public Node left;

    public Node right;

    public Node(int value) {

    this.value = value;

    }

    }

    }

    /* 如有意见或建议,欢迎评论区留言;如发现代码有误,欢迎批评指正 */

    展开全文
  • 662. 二叉树最大宽度给定一个二叉树,编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与满二叉树(full binary tree)结构相同,但一些节点为空。每一层的宽度被定义为两个端点(该层最...

    662. 二叉树最大宽度

    给定一个二叉树,编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与满二叉树(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)。

    注意: 答案在32位有符号整数的表示范围内。

    PS:

    min就是我这一层最左面的点

    max就是我右面的点,每一次进去,只要比最左面大,就保存

    右面的点–左面的点=我这一层的大小

    左面的就是val2-1,我如果有左面的就是我每一层会乘2,然后左面就是减去1

    右面的就是val2;

    自己带一个树试试就明白了,我当时也想了半天才明白

    /**

    * Definition for a binary tree node.

    * public class TreeNode {

    * int val;

    * TreeNode left;

    * TreeNode right;

    * TreeNode(int x) { val = x; }

    * }

    */

    class Solution {

    class Node {

    int min, max;

    Node next;

    }

    private void calNode(TreeNode node, int val, Node level ){

    if (level.min==0) {

    level.min=val;

    level.max=val;

    } else if (val>level.max) {

    level.max=val;

    }

    if (node.left==null && node.right==null) return;

    if (level.next==null) level.next = new Node();

    if (node.left!=null) calNode(node.left, val*2-1, level.next);

    if (node.right!=null) calNode(node.right, val*2, level.next);

    }

    public int widthOfBinaryTree(TreeNode root) {

    if (root==null) return 0;

    Node level = new Node();

    calNode(root, 1, level);

    int k, res=0;

    while (level!=null){

    k = level.max - level.min + 1;

    if (k>res) res = k;

    level = level.next;

    }

    return res;

    }

    }

    Leetcode 662&period;二叉树最大宽度

    二叉树最大宽度 给定一个二叉树,编写一个函数来获取这个树的最大宽度.树的宽度是所有层中的最大宽度.这个二叉树与满二叉树(full binary tree)结构相同,但一些节点为空. 每一层的宽度被定义 ...

    Java实现 LeetCode 297 二叉树的序列化与反序列化

    297. 二叉树的序列化与反序列化 序列化是将一个数据结构或者对象转换为连续的比特位的操作,进而可以将转换后的数据存储在一个文件或者内存中,同时也可以通过网络传输到另一个计算机环境,采取相反方式重构得 ...

    LeetCode:二叉树的非递归中序遍历

    第一次动手写二叉树的,有点小激动,64行的if花了点时间,上传leetcode一次点亮~~~ /* inorder traversal binary tree */ #include

    Java实现 LeetCode 199 二叉树的右视图

    199. 二叉树的右视图 给定一棵二叉树,想象自己站在它的右侧,按照从顶部到底部的顺序,返回从右侧所能看到的节点值. 示例: 输入: [1,2,3,null,5,null,4] 输出: [1, 3, ...

    Java实现 LeetCode 145 二叉树的后序遍历

    145. 二叉树的后序遍历 给定一个二叉树,返回它的 后序 遍历. 示例: 输入: [1,null,2,3] 1 \ 2 / 3 输出: [3,2,1] 进阶: 递归算法很简单,你可以通过迭代算法完成 ...

    &lbrack;LeetCode&rsqb; 543&period; 二叉树的直径 &star;&lpar;递归、数最大深度&rpar;

    描述 给定一棵二叉树,你需要计算它的直径长度.一棵二叉树的直径长度是任意两个结点路径长度中的最大值.这条路径可能穿过根结点. 示例 :给定二叉树 1 / \ 2 3 / \ 4 5 返回 3, 它的长 ...

    Java实现 LeetCode 814 二叉树剪枝 (遍历树)

    814. 二叉树剪枝 给定二叉树根结点 root ,此外树的每个结点的值要么是 0,要么是 1. 返回移除了所有不包含 1 的子树的原二叉树. ( 节点 X 的子树为 X 本身,以及所有 X 的后代. ...

    Java实现 LeetCode 671 二叉树中第二小的节点(遍历树)

    671. 二叉树中第二小的节点 给定一个非空特殊的二叉树,每个节点都是正数,并且每个节点的子节点数量只能为 2 或 0.如果一个节点有两个子节点的话,那么这个节点的值不大于它的子节点的值. 给出这样的 ...

    Java实现 LeetCode 637 二叉树的层平均值(遍历树)

    637. 二叉树的层平均值 给定一个非空二叉树, 返回一个由每层节点平均值组成的数组. 示例 1: 输入: 3 / \ 9 20 / \ 15 7 输出: [3, 14.5, 11] 解释: 第0层的 ...

    随机推荐

    HDOJ 1009&period; Fat Mouse&&num;39&semi; Trade 贪心 结构体排序

    FatMouse' Trade Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) ...

    使用属性动画 &mdash&semi; Property Animation

    属性动画,就是通过控制对象中的属性值产生的动画.属性动画是目前最高级的2D动画系统. 在API Level 11中添加.Property Animation号称能控制一切对象的动画,包括可见的和不可见 ...

    关于IE8及其以下的IE版本不支持getElementsByClassName

    之前做一下项目的时候知道IE8以及其以下的版本不支持getElementsByClassName,于是乎自己写了一个函数重新定义getElementsByClassName,函数代码如下: funct ...

    个人总结 HTML&plus;CSS

    从大一下学期接触,一直到今年,接触的时间也挺长的了,最近一些认识的盆友和同学说是想学习前端,自己也开始慢慢停下脚步,不再拼命地去学很多框架的东西,回归到基础,慢慢把基础打牢 很多知识碎片一直来不及整理 ...

    OpenStack 新加计算节点后修改

    Contents [hide] 1 前提 2 iptables禁止snat= 3 vlan支持 4 Quota支持 5 修改物理资源设置. 6 添加collectd 7 重启服务 前提 我们使用fue ...

    struts2源码调试环境的搭建

    源码之前,了无秘密. 说一句逼格很高的话来镇镇场子. 这两天在看陆舟的,一边看脑子一边冒出四个字:相见恨晚.极力推荐想了解Struts2的人看看这本书,之前一直在 ...

    HTML5----input-datalist输入框自己主动提示功能

    效果图: 字母 :

    JSON数据传递

    Servlet端代码 try { while (rs.next()) { for(int i=0;i<60;i++){ Day[i]+=rs.getInt("Day"+(i+ ...

    洛古 P2568 莫比乌斯&plus;暴力

    #include #define LL long long using namespace std; ; bool vis[maxn]; int prime[ ...

    java&period;lang&period;OutOfMemoryError:GC overhead limit exceeded解决方法

    异常如下:Exception in thread "main" java.lang.OutOfMemoryError: GC overhead limit exceeded 一.解 ...

    展开全文
  • 662. 二叉树最大宽度

    2021-03-26 16:06:46
    662. 二叉树最大宽度 给定一个二叉树,编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与满二叉树(full binary tree)结构相同,但一些节点为空。 每一层的宽度被定义为两个端点...

    662. 二叉树最大宽度

    原始题目链接:https://leetcode-cn.com/problems/maximum-width-of-binary-tree/
    给定一个二叉树,编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与满二叉树(full binary tree)结构相同,但一些节点为空。

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

    在这里插入图片描述

    在这里插入图片描述
    解题思路:

    利用满二叉树的性质,当前节点的坐标和其对应的左右子树节点的坐标的关系,当前节点的坐标是i,则左孩子节点的坐标是2i,有孩子节点的坐标是2i+1。由于是利用满二叉树,所以使用层序遍历树的形式较为合适,遍历到最底层的节点后,计算最右侧的孩子和最左侧的孩子的节点坐标的差值+1,即为最后的答案。具体实现看代码及注释。

    代码实现:

    # Definition for a binary tree node.
    # class TreeNode:
    #     def __init__(self, val=0, left=None, right=None):
    #         self.val = val
    #         self.left = left
    #         self.right = right
    class Solution:
        def widthOfBinaryTree(self, root: TreeNode) -> int:
            # 边界检测
            if not root:
                return 0
            # 利用满二叉树的性质,当前节点的坐标值是value,左孩子的坐标值是2*value,右孩子的坐标值是2*value+1
            # 用队列模拟,队列的元素是元组,元组的元素存储当前节点的坐标(从0开始)和当前节点
            queue = [(0, root)]
            ans = 1
            while queue:
                # 宽度的计算是最右侧节点坐标 - 最左侧节点的坐标 + 1
                ans = max(ans, queue[-1][0] - queue[0][0] + 1)
                # 更新队列,使用临时空队列替换更新
                temp = []
                for loc, node in queue:
                    # 注意左右节点的入队顺序
                    node.left and temp.append((loc * 2, node.left))
                    node.right and temp.append((loc * 2 + 1, node.right))
                # 更新队列里的元素
                queue = temp
            
            return ans
    

    参考文献:
    https://leetcode-cn.com/problems/maximum-width-of-binary-tree/solution/662-er-cha-shu-zui-da-kuan-du-ceng-ci-bian-li-by-t/

    展开全文
  • 662. 二叉树最大宽度 给定一个二叉树,编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与满二叉树(full binary tree)结构相同,但一些节点为空。 每一层的宽度被定义为两个端点...
  • 662. 二叉树最大宽度 给定一个二叉树,编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与满二叉树(full binary tree)结构相同,但一些节点为空。 每一层的宽度被定义为两个端点...
  • 二叉树最大宽度 给定一个二叉树,编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与满二叉树(full binary tree)结构相同,但一些节点为空。 每一层的宽度被定义为两个端点...
  • 二叉树最大宽度 /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * };...
  • leetcode 662 : 二叉树最大宽度题目描述解法我的思路官方题解方法一:宽度优先搜索 BFS方法二:深度优先搜索 DFS 题目描述 给定一个二叉树,编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这...
  • 二叉树最大宽度 给定一个二叉树,编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与满二叉树(full binary tree)结构相同,但一些节点为空。 每一层的宽度被定义为两个端点(该...
  • 二叉树最大宽度 题目 给定一个二叉树,编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与满二叉树(full binary tree)结构相同,但一些节点为空。 每一层的宽度被定义为两个端点...
  • 1501 二叉树最大宽度和高度 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 白银 Silver题解 查看运行结果题目描述 Description 给出一个二叉树,输出它的最大宽度和高度。输入描述 Input Description第一行...
  • 1501 二叉树最大宽度和高度 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 白银 Silver 题目描述 Description 给出一个二叉树,输出它的最大宽度和高度。 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 564
精华内容 225
关键字:

二叉树最大宽度