二叉树的最大宽度系列问题

二叉树的最大宽度系列问题

作者：Grey

原文地址：

博客园：二叉树的最大宽度系列问题

CSDN：二叉树的最大宽度系列问题

求树的最大宽度

题目描述

给你一棵二叉树的根节点 root ，返回树的最大宽度 。
树的最大宽度是所有层中最大的宽度 。
每一层的宽度被定义为该层最左和最右的非空节点（即，两个端点）之间的长度。
将这个二叉树视作与满二叉树结构相同，两端点间会出现一些延伸到这一层的 null 节点，这些 null 节点也计入长度。

题目链接：LeetCode 662. Maximum Width of Binary Tree

主要思路

由于求宽度的时候，可以把这个二叉树视作满二叉树，所以在原先的 TreeNode 基础上，封装一个数据结构

    static class AnnotateNode {         TreeNode treeNode;         int depth;         int pos;          public AnnotateNode(TreeNode treeNode, int depth, int pos) {             this.treeNode = treeNode;             this.depth = depth;             this.pos = pos;         }     } 

这个数据结构增加了两个数据项：

depth：表示一个 TreeNode 节点在第几层。

pos：表示一个 TreeNode 节点在当前层排第几（注：空节点也算）。

以一颗二叉树举例，如下示例图，以两个节点来说明封装的 AnnotateNode，虚线节点是 null 节点。

对于一棵满二叉树来说，如果当前节点是 depth，pos，那么其左孩子就是 depth + 1，pos * 2；右孩子就是 depth + 1，pos * 2 + 1。

接下来，并把每个位置的 pos，depth 指标记录到 AnnotateNode 节点中。

参考二叉树的按层遍历对二叉树进行遍历，在下一层开始结算上一层的结果。

而且每次要记录上一层的最左位置 left，在一层结束时，记录一个最右侧位置 right，然后设置一个全局最大的 max，max 的更新策略就是

max = Math.max(max, right - left + 1) 

完整代码见

class Solution {         public int widthOfBinaryTree(TreeNode root) {         if (root == null) {             return 0;         }         int max = 1;         Queue<AnnotateNode> queue = new LinkedList<>();         queue.offer(new AnnotateNode(root, 0, 0));         int curDepth = 0;         int left = 0;         while (!queue.isEmpty()) {             AnnotateNode node = queue.poll();             if (node.treeNode != null) {                 queue.offer(new AnnotateNode(node.treeNode.left, node.depth + 1, node.pos * 2));                 queue.offer(new AnnotateNode(node.treeNode.right, node.depth + 1, node.pos * 2 + 1));                 if (curDepth != node.depth) {                     curDepth = node.depth;                     left = node.pos;                 }                 int right = node.pos;                 max = Math.max(max, right - left + 1);             }         }         return max;     }      static class AnnotateNode {         TreeNode treeNode;         int depth;         int pos;          public AnnotateNode(TreeNode treeNode, int depth, int pos) {             this.treeNode = treeNode;             this.depth = depth;             this.pos = pos;         }     } } 

求树的最大宽度的有效节点个数

题目描述

给定一个二叉树，你需要编写一个函数来获取这课树的最大宽度，二叉树的最大宽度是指具有节点数最多的那一层的结点个数。

题目链接见：牛客-二叉树的最大宽度

与上一个问题不同，本题求的最大宽度是有效节点的个数，所以是不包括 null 节点的。

主要思路

可以使用哈希表，并且按照层次遍历的方法，存下每一层的节点个数。不过还有更省空间的做法，设置有限几个变量，无需申请一个哈希表

// 当前层的结尾节点，初始为 head  TreeNode curEnd = head; // 下一层的结尾节点，初始为 null TreeNode nextEnd = null; // 当前层的节点个数，初始化为 0 int curLevelNodes = 0; 

然后也是二叉树的按层遍历对二叉树进行遍历，遍历过程中，如果遍历到的当前节点 c 满足 c == curEnd，即：当前节点就是当前结尾位置的节点，则可以确定一层结束，更新全局 max，当前层节点个数归零，即 curLevelNodes = 0，并将下层结尾节点赋值给 curEnd。

max = Math.max(curLevelNodes, max); curLevelNodes = 0; curEnd = nextEnd; 

完整代码见

public class Solution {     public  int getMaxWidth(TreeNode head) {         if (head == null) {             return 0;         }         Queue<TreeNode> queue = new LinkedList<>();         int max = 1;         queue.offer(head);          TreeNode curEnd = head;         TreeNode nextEnd = null;         int curLevelNodes = 0;         while (!queue.isEmpty()) {             TreeNode c = queue.poll();             if (c.left != null) {                 queue.offer(c.left);                 nextEnd = c.left;             }             if (c.right != null) {                 queue.offer(c.right);                 nextEnd = c.right;             }             curLevelNodes++;             // 当前节点已经到结束了             if (c == curEnd) {                 max = Math.max(curLevelNodes, max);                 curLevelNodes = 0;                 curEnd = nextEnd;             }         }         return max;     } } 

更多

算法和数据结构笔记