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

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

作者: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 节点。

image

对于一棵满二叉树来说,如果当前节点是 depth,pos,那么其左孩子就是 depth + 1pos * 2;右孩子就是 depth + 1pos * 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;
    }
}

更多

算法和数据结构笔记