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

二叉树,最大,宽度,系列,问题 · 浏览次数 : 283

小编点评

```python class AnnotateNode: def __init__(self, treeNode, depth, pos): self.treeNode = treeNode self.depth = depth self.pos = pos class Solution: def widthOfBinaryTree(self, root: TreeNode) -> int: # 使用队列来实现层级遍历 max_width = 1 queue = [AnnotateNode(root, 0, 0)] depth = 0 left = 0 while queue: node = queue.pop(0) if node.treeNode: # 将当前节点的所有子节点加入队列中 queue.append(AnnotateNode(node.treeNode.left, node.depth + 1, node.pos * 2)) queue.append(AnnotateNode(node.treeNode.right, node.depth + 1, node.pos * 2 + 1)) if depth != node.depth: depth = node.depth left = node.pos # 更新最大宽度 max_width = max(max_width, right - left + 1) # 每个层都只有一个最左和最右位置的节点，更新全局最大宽度 curLevelNodes = 0 # 遍历完当前节点，则到下一层 if node.treeNode: nextEnd = node.treeNode.right if node.treeNode.right else None curLevelNodes += 1 if node == curEnd: max_width = max(max_width, curLevelNodes) curLevelNodes = 0 curEnd = nextEnd return max_width ``` **代码说明：** * `AnnotateNode` 类用于封装每个节点的信息，包括树节点、深度和位置。 * `widthOfBinaryTree` 函数使用队列实现层级遍历。 * 每次遍历到当前节点的末端，更新最大宽度。 * `max_width` 用于存储最终的最大宽度。 * 对于每个节点，如果其子节点不为空，将其添加到队列中。 * 每个层都只有一个最左和最右位置的节点，因此更新 `max_width` 时只记录最右的位置。

正文

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

作者：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;
    }
}

算法和数据结构笔记