18924 二叉树的宽度
时间: 2023-11-18 21:29:16 浏览: 39
二叉树的宽度是指二叉树中某一层节点数的最大值。可以通过层序遍历二叉树,在遍历每一层节点时统计节点个数,取最大值即为二叉树的宽度。以下是一段示例代码(假设二叉树的节点结构定义如下):
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def width_of_binary_tree(root: TreeNode) -> int:
if not root:
return 0
max_width = 0
queue = [(root, 1)] # 记录节点和节点编号
while queue:
level_size = len(queue)
_, level_start = queue[0]
for i in range(level_size):
node, pos = queue.pop(0)
if node.left:
queue.append((node.left, pos * 2))
if node.right:
queue.append((node.right, pos * 2 + 1))
max_width = max(max_width, pos - level_start + 1)
return max_width
```
在上述代码中,使用一个队列来进行层序遍历,在队列中同时记录节点和节点编号(根节点编号为1,左子节点编号是父节点编号的两倍,右子节点编号是父节点编号的两倍加一)。在遍历每一层节点时,先记录下该层第一个节点的编号,然后计算出最后一个节点的编号,两者相减再加一即为该层节点个数。遍历完所有层后,取所有层节点个数中的最大值即为二叉树的宽度。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)