二叉树的最大宽度

[编程题]二叉树的最大宽度

热度指数：2350 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个二叉树，请你求出此二叉树的最大宽度。

本题中树第 i 层的宽度定义为：第 i 层最左边的节点到最右边之间的距离，中间空节点也计入距离。

例如：

本树中第 1 层只有一个节点，故第 1 层宽度是 1 ，第二层最左侧到最右侧的距离是 2 ，所以宽度是 2 ，第三层最左侧 4 到最右侧 5 距离是 4 ，故宽度是 4，此树最大宽度是 4。

示例1

输入

{1,2,3,4,#,4,5}

输出

说明

如题面图

示例2

输入

{1}

输出

示例3

输入

{1,2,3,4,#,4,5,6,#,1}

输出

说明

倒数第二层的宽度为5

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

算法知识视频讲解

Python3

liangzhengjie

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param root TreeNode类 
# @return int整型
#
class Solution:
    def widthOfBinaryTree(self , root: TreeNode) -> int:
        # write code here
        if not root:
            return False

        q = []
        q.append(root)

        res = 0
        while len(q) != 0:
            left = 0
            right = len(q)
            while q[left] is None:
                left += 1
            while q[right - 1] is None:
                right -= 1
            res = max(res, right - left)

            next_q = []
            have_next = False
            for index in range(len(q)):
                node = q[index]

                if node is None:
                    next_q.append(None)
                    next_q.append(None)
                    continue

                if node.left:
                    have_next = True
                    next_q.append(node.left)
                else:
                    next_q.append(None)

                if node.right:
                    have_next = True
                    next_q.append(node.right)
                else:
                    next_q.append(None)

            if have_next:
                q = next_q
            else:
                q = []

        return res

发表于 2024-04-27 23:16:50 回复(0)