力扣每日练习（3.19）补

本文主要是介绍力扣每日练习（3.19）补，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

958. 二叉树的完全性检验

根据完全的定义，可以知道是最后一层的节点要尽可能靠近左边，那么不成立的条件就是最后一层的节点是这样的[1,4,56,null,13]
也就是第一个空节点后竟然还有非空节点，违背了完全。

所以采用层序遍历的方式，将每层的节点都检查是否null是连续的。这样不仅考虑了最后一层的情况，还考虑到了中间层有null的情况。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def isCompleteTree(self, root: Optional[TreeNode]) -> bool:# 层序遍历queue = [root]# 初始化标记is_empty = Falsewhile queue:level_size = len(queue)for _ in range(level_size):# 检查每个节点node = queue.pop(0)# 节点为空，则将指示变量设为Trueif node is None:is_empty = Trueelse: # 否则，检查指示变量是否为True，如果是，则代表前面有空节点，不是完全了if is_empty: return False# 不为空，继续检查左右子树，空的也要加queue.append(node.left)queue.append(node.right)return is_empty

543. 二叉树的直径

二叉树的直径不一定通过根节点，它可以是：
经过根节点的最长路径，这条路径由根节点的左子树的最大深度和右子树的最大深度组成。
完全位于左子树内的最长路径。
完全位于右子树内的最长路径。

因此，对于每个节点，我们需要计算两部分：
经过该节点的最长路径长度（这不是直径，除非该节点恰好是直径的根节点）。这等于该节点左子树的深度加上右子树的深度。
该节点子树的深度，以便于父节点计算经过自身的最长路径长度。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:self.diameter = 0def depth(node):if not node:return 0left_depth = depth(node.left)  # 计算左子树的深度right_depth = depth(node.right)  # 计算右子树的深度# 更新直径self.diameter = max(self.diameter, left_depth + right_depth)# 返回节点的深度return max(left_depth, right_depth) + 1depth(root)  # 从根节点开始递归return self.diameter

662. 二叉树最大宽度

最大宽度，中间如果是空也记上。很自然想到层序遍历，但是最大宽度不能像层序那样只记录非空节点，所以要引入索引

可以将其视为一个满二叉树，其性质就是

在一个完全二叉树（或任意二叉树，但我们用完全二叉树的性质来帮助我们进行计算）中，如果我们假设根节点的索引为0，则对于任意一个节点，其左子节点的索引为2 * index + 1，其右子节点的索引为2 * index + 2，其中index是该节点的索引。

所以就根据其索引，遇到非空的节点的左右子树，直接在队列中增加其节点和索引。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:if not root: return 0max_width = 0queue = [(root, 0)]  # 队列中存储（节点，索引）while queue:level_size = len(queue)_, first_index = queue[0]  # 当前层第一个节点的索引_, last_index = queue[-1]  # 当前层最后一个节点的索引max_width = max(max_width, last_index - first_index + 1)for _ in range(level_size):node, index = queue.pop(0)# 利用满二叉树的性质if node.left:queue.append((node.left, index * 2 +1))if node.right:queue.append((node.right, index * 2 +2))return max_width

这篇关于力扣每日练习（3.19）补的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---