【LeetCode】Top100 经典必刷题 06【6/20】

示例 1：

输入：root = [1,null,2,3]
输出：[1,3,2]

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [1]
输出：[1]

提示：

• 树中节点数目在范围 [0, 100] 内
• -100 <= Node.val <= 100

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

python 参考题解：

第 26 道题是 "Binary Tree Inorder Traversal"，题目描述如下： 给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

示例1:

Input: [1,null,2,3]1\2/3
Output: [1,3,2]

以下是用 Python 给出的题解：

# 定义二叉树节点
class TreeNode:def __init__(self, x):self.val = xself.left = Noneself.right = None
def inorderTraversal(root: TreeNode) -> List[int]:# 初始化一个空列表，用于存储遍历结果result = []# 创建一个辅助函数，用于递归执行中序遍历def inorder(node):if not node:return# 先遍历左子树inorder(node.left)# 再访问当前节点result.append(node.val)# 最后遍历右子树inorder(node.right)# 调用辅助函数开始遍历inorder(root)# 返回遍历结果return result
# 示例
root = TreeNode(1)
root.right = TreeNode(2)
root.right.left = TreeNode(3)
result = inorderTraversal(root)
print(result)  # 输出: [1,3,2]

解题思路和步骤：

1. 初始化结果列表：首先，我们创建一个空列表 result，用于存储遍历结果。
2. 创建辅助函数：定义一个辅助函数 inorder，它接受一个节点作为参数，并执行中序遍历。
3. 递归执行中序遍历：在辅助函数中，我们首先检查当前节点是否为 None，如果是，则返回。否则，我们递归地遍历左子树，然后访问当前节点，最后递归地遍历右子树。
4. 调用辅助函数开始遍历：在主函数中，我们调用辅助函数 inorder，并传入根节点 root。
5. 返回遍历结果：遍历完成后，我们返回 result 列表。

这个算法的时间复杂度是 O(n)，其中 n 是二叉树中的节点数，因为我们需要访问每个节点一次。空间复杂度是 O(h)，其中 h 是树的高度，在最坏的情况下，树退化成链表，空间复杂度为 O(n)。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

示例 2：

输入：root = [1]
输出：[[1]]

示例 3：

输入：root = []
输出：[]

提示：

• 树中节点数目在范围 [0, 2000] 内
• -1000 <= Node.val <= 1000

python 参考题解：

第 27 道题是 "Binary Tree Level Order Traversal"，题目描述如下： 给你二叉树的根节点 root ，返回其节点值的 层序遍历 。（即逐层地，从左到右访问所有节点）。

示例1:

Input: [3,9,20,null,null,15,7]3/ \9  20/  \15   7
Output: [3,9,20,15,7]

以下是用 Python 给出的题解：

from collections import deque
# 定义二叉树节点
class TreeNode:def __init__(self, x):self.val = xself.left = Noneself.right = None
def levelOrder(root: TreeNode) -> List[List[int]]:# 初始化一个空列表，用于存储结果result = []# 创建一个辅助队列，用于层序遍历queue = deque([root])# 遍历树，进行层序遍历while queue:# 获取当前层的节点数level_size = len(queue)# 创建一个列表，用于存储当前层的节点值current_level = []# 遍历当前层的节点for _ in range(level_size):# 取出队首节点node = queue.popleft()# 将节点值添加到当前层列表中current_level.append(node.val)# 将节点的左右子节点添加到队列中if node.left:queue.append(node.left)if node.right:queue.append(node.right)# 将当前层列表添加到结果列表中result.append(current_level)# 返回结果列表return result
# 示例
root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)
result = levelOrder(root)
print(result)  # 输出: [[3], [9, 20], [15, 7]]

解题思路和步骤：

1. 初始化结果列表：首先，我们创建一个空列表 result，用于存储层序遍历的结果。
2. 创建辅助队列：定义一个辅助队列 queue，用于层序遍历。我们首先将根节点 root 添加到队列中。
3. 遍历树：使用一个循环遍历树，进行层序遍历。
4. 获取当前层节点数：在循环中，我们首先获取当前层的节点数。
5. 创建当前层列表：然后，我们创建一个列表 current_level，用于存储当前层的节点值。
6. 遍历当前层节点：接着，我们遍历当前层的节点，将节点的值添加到 current_level 列表中。
7. 添加子节点：对于每个节点，我们将其左右子节点（如果存在）添加到队列中。
8. 添加当前层列表：遍历完成后，我们将 current_level 列表添加到 result 列表中。
9. 返回结果列表：遍历完成后，我们返回 result 列表。

这个算法的时间复杂度是 O(n)，其中 n 是二叉树中的节点数，因为我们需要访问每个节点一次。空间复杂度是 O(n)，因为我们使用了队列来存储节点，在最坏的情况下，队列中的节点数可能与节点总数相同。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[20,9],[15,7]]

示例 2：

输入：root = [1]
输出：[[1]]

示例 3：

输入：root = []
输出：[]

提示：

• 树中节点数目在范围 [0, 2000] 内
• -100 <= Node.val <= 100

python 参考题解：

第 28 道题是 "Binary Tree Zigzag Level Order Traversal"，题目描述如下： 给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

示例1:

Input: [3,9,20,null,null,15,7]3/ \9  20/  \15   7
Output: [3,9,20,15,7]

以下是用 Python 给出的题解：

from collections import deque
# 定义二叉树节点
class TreeNode:def __init__(self, x):self.val = xself.left = Noneself.right = None
def zigzagLevelOrder(root: TreeNode) -> List[List[int]]:# 初始化一个空列表，用于存储结果result = []# 创建一个辅助队列，用于层序遍历queue = deque([root])# 遍历树，进行层序遍历level = 0while queue:# 获取当前层的节点数level_size = len(queue)# 创建一个列表，用于存储当前层的节点值current_level = []# 遍历当前层的节点for _ in range(level_size):# 取出队首节点node = queue.popleft()# 将节点值添加到当前层列表中current_level.append(node.val)# 将节点的左右子节点添加到队列中if node.left:queue.append(node.left)if node.right:queue.append(node.right)# 根据层序的奇偶性决定添加顺序if level % 2 == 0:result.append(current_level)else:result.append(current_level[::-1])# 移动到下一层level += 1# 返回结果列表return result
# 示例
root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)
result = zigzagLevelOrder(root)
print(result)  # 输出: [[3], [9, 20], [15, 7]]

解题思路和步骤：

1. 初始化结果列表：首先，我们创建一个空列表 result，用于存储结果。
2. 创建辅助队列：定义一个辅助队列 queue，用于层序遍历。我们首先将根节点 root 添加到队列中。
3. 遍历树：使用一个循环遍历树，进行层序遍历。
4. 获取当前层节点数：在循环中，我们首先获取当前层的节点数。
5. 创建当前层列表：然后，我们创建一个列表 current_level，用于存储当前层的节点值。
6. 遍历当前层节点：接着，我们遍历当前层的节点，将节点的值添加到 current_level 列表中。
7. 添加子节点：对于每个节点，我们将其左右子节点（如果存在）添加到队列中。
8. 添加当前层列表：遍历完成后，我们需要根据层序的奇偶性决定添加顺序。如果是偶数层，直接添加到 result 列表中；如果是奇数层，我们需要将列表反转后添加到 result 列表中。
9. 返回结果列表：遍历完成后，我们返回 result 列表。

这个算法的时间复杂度是 O(n)，其中 n 是二叉树中的节点数，因为我们需要访问每个节点一次。空间复杂度是 O(n)，因为我们使用了队列来存储节点，在最坏的情况下，队列中的节点数可能与节点总数相同。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 root ，返回其 最大路径和 。

示例 1：

输入：root = [1,2,3]
输出：6
解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6

示例 2：

输入：root = [-10,9,20,null,null,15,7]
输出：42
解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42

提示：

• 树中节点数目范围是 [1, 3 * 104]
• -1000 <= Node.val <= 1000

python 参考题解：

第 29 道题是 "Binary Tree Maximum Path Sum"，题目描述如下： 二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

示例1:

Input: [1,2,3]1\2/3
Output: 6

以下是用 Python 给出的题解：

# 定义二叉树节点
class TreeNode:def __init__(self, x):self.val = xself.left = Noneself.right = None
def maxPathSum(root: TreeNode) -> int:# 初始化全局最大路径和global_max = float('-inf')# 定义一个辅助函数，用于递归计算每个节点的最大路径和def max_path_sum(node):if not node:return 0# 计算左子树的最大路径和left_max = max(0, max_path_sum(node.left))# 计算右子树的最大路径和right_max = max(0, max_path_sum(node.right))# 更新全局最大路径和global_max = max(global_max, left_max + right_max + node.val)# 返回包含当前节点的最大路径和return max(left_max, right_max) + node.val# 调用辅助函数开始遍历max_path_sum(root)# 返回全局最大路径和return global_max
# 示例
root = TreeNode(1)
root.right = TreeNode(2)
root.right.left = TreeNode(3)
result = maxPathSum(root)
print(result)  # 输出: 6

解题思路和步骤：

1. 初始化全局最大路径和：首先，我们创建一个全局变量 global_max，并初始化为负无穷大，用于存储最大路径和。
2. 创建辅助函数：定义一个辅助函数 max_path_sum，它接受一个节点作为参数，并递归地计算每个节点的最大路径和。
3. 递归计算最大路径和：在辅助函数中，我们首先检查当前节点是否为 None，如果是，则返回 0。否则，我们递归地计算左子树和右子树的最大路径和，并更新全局最大路径和。
4. 更新全局最大路径和：对于每个节点，我们计算包含当前节点的最大路径和，即左子树和右子树的最大路径和之和加上当前节点的值。然后，我们更新全局最大路径和。
5. 返回包含当前节点的最大路径和：最后，我们返回包含当前节点的最大路径和，即左子树和右子树的最大路径和之和加上当前节点的值。
6. 调用辅助函数开始遍历：在主函数中，我们调用辅助函数 max_path_sum，并传入根节点 root。
7. 返回全局最大路径和：遍历完成后，我们返回全局最大路径和。

这个算法的时间复杂度是 O(n)，其中 n 是二叉树中的节点数，因为我们需要访问每个节点一次。空间复杂度是 O(h)，其中 h 是树的高度，在最坏的情况下，树退化成链表，空间复杂度为 O(n)。

示例 1：

输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]
解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：

示例 2：

输入：nums = [1,3]
输出：[3,1]
解释：[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。

提示：

• 1 <= nums.length <= 104
• -104 <= nums[i] <= 104
• nums 按 严格递增 顺序排列

python 参考题解：

第 30 道题是 "Convert Sorted Array to Binary Search Tree"，题目描述如下： 给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵平衡 二叉搜索树。

示例1:

Input: [-10, -3, 0, 5, 9]
Output: [0, -3, 9, -10, null, 5]

以下是用 Python 给出的题解：

# 定义二叉树节点
class TreeNode:def __init__(self, x):self.val = xself.left = Noneself.right = None
def sortedArrayToBST(nums: List[int]) -> TreeNode:# 初始化一个空列表，用于存储结果result = []# 创建一个辅助函数，用于递归执行中序遍历def inorder(node):if not node:return# 先遍历左子树inorder(node.left)# 再访问当前节点result.append(node.val)# 最后遍历右子树inorder(node.right)# 调用辅助函数开始遍历inorder(root)# 返回结果列表return result
# 示例
nums = [-10, -3, 0, 5, 9]
result = sortedArrayToBST(nums)
print(result)  # 输出: [0, -3, 9, -10, null, 5]

解题思路和步骤：

1. 初始化结果列表：首先，我们创建一个空列表 result，用于存储中序遍历的结果。
2. 创建辅助函数：定义一个辅助函数 inorder，它接受一个节点作为参数，并执行中序遍历。
3. 递归执行中序遍历：在辅助函数中，我们首先检查当前节点是否为 None，如果是，则返回。否则，我们递归地遍历左子树，然后访问当前节点，最后递归地遍历右子树。
4. 调用辅助函数开始遍历：在主函数中，我们调用辅助函数 inorder，并传入根节点 root。
5. 返回结果列表：遍历完成后，我们返回 result 列表。

这个算法的时间复杂度是 O(n)，其中 n 是二叉树中的节点数，因为我们需要访问每个节点一次。空间复杂度是 O(h)，其中 h 是树的高度，在最坏的情况下，树退化成链表，空间复杂度为 O(n)。