【LeetCode】Top100 经典必刷题 06【6/20】
给定一个二叉树的根节点 root
,返回 它的 中序 遍历 。
示例 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]
解题思路和步骤:
- 初始化结果列表:首先,我们创建一个空列表
result
,用于存储遍历结果。 - 创建辅助函数:定义一个辅助函数
inorder
,它接受一个节点作为参数,并执行中序遍历。 - 递归执行中序遍历:在辅助函数中,我们首先检查当前节点是否为
None
,如果是,则返回。否则,我们递归地遍历左子树,然后访问当前节点,最后递归地遍历右子树。 - 调用辅助函数开始遍历:在主函数中,我们调用辅助函数
inorder
,并传入根节点root
。 - 返回遍历结果:遍历完成后,我们返回
result
列表。
这个算法的时间复杂度是 O(n),其中 n 是二叉树中的节点数,因为我们需要访问每个节点一次。空间复杂度是 O(h),其中 h 是树的高度,在最坏的情况下,树退化成链表,空间复杂度为 O(n)。
给你二叉树的根节点 root
,返回其节点值的 层序遍历 。 (即逐层地,从左到右访问所有节点)。
示例 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]]
解题思路和步骤:
- 初始化结果列表:首先,我们创建一个空列表
result
,用于存储层序遍历的结果。 - 创建辅助队列:定义一个辅助队列
queue
,用于层序遍历。我们首先将根节点root
添加到队列中。 - 遍历树:使用一个循环遍历树,进行层序遍历。
- 获取当前层节点数:在循环中,我们首先获取当前层的节点数。
- 创建当前层列表:然后,我们创建一个列表
current_level
,用于存储当前层的节点值。 - 遍历当前层节点:接着,我们遍历当前层的节点,将节点的值添加到
current_level
列表中。 - 添加子节点:对于每个节点,我们将其左右子节点(如果存在)添加到队列中。
- 添加当前层列表:遍历完成后,我们将
current_level
列表添加到result
列表中。 - 返回结果列表:遍历完成后,我们返回
result
列表。
这个算法的时间复杂度是 O(n),其中 n 是二叉树中的节点数,因为我们需要访问每个节点一次。空间复杂度是 O(n),因为我们使用了队列来存储节点,在最坏的情况下,队列中的节点数可能与节点总数相同。
给你二叉树的根节点 root
,返回其节点值的 锯齿形层序遍历 。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。
示例 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]]
解题思路和步骤:
- 初始化结果列表:首先,我们创建一个空列表
result
,用于存储结果。 - 创建辅助队列:定义一个辅助队列
queue
,用于层序遍历。我们首先将根节点root
添加到队列中。 - 遍历树:使用一个循环遍历树,进行层序遍历。
- 获取当前层节点数:在循环中,我们首先获取当前层的节点数。
- 创建当前层列表:然后,我们创建一个列表
current_level
,用于存储当前层的节点值。 - 遍历当前层节点:接着,我们遍历当前层的节点,将节点的值添加到
current_level
列表中。 - 添加子节点:对于每个节点,我们将其左右子节点(如果存在)添加到队列中。
- 添加当前层列表:遍历完成后,我们需要根据层序的奇偶性决定添加顺序。如果是偶数层,直接添加到
result
列表中;如果是奇数层,我们需要将列表反转后添加到result
列表中。 - 返回结果列表:遍历完成后,我们返回
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
解题思路和步骤:
- 初始化全局最大路径和:首先,我们创建一个全局变量
global_max
,并初始化为负无穷大,用于存储最大路径和。 - 创建辅助函数:定义一个辅助函数
max_path_sum
,它接受一个节点作为参数,并递归地计算每个节点的最大路径和。 - 递归计算最大路径和:在辅助函数中,我们首先检查当前节点是否为
None
,如果是,则返回 0。否则,我们递归地计算左子树和右子树的最大路径和,并更新全局最大路径和。 - 更新全局最大路径和:对于每个节点,我们计算包含当前节点的最大路径和,即左子树和右子树的最大路径和之和加上当前节点的值。然后,我们更新全局最大路径和。
- 返回包含当前节点的最大路径和:最后,我们返回包含当前节点的最大路径和,即左子树和右子树的最大路径和之和加上当前节点的值。
- 调用辅助函数开始遍历:在主函数中,我们调用辅助函数
max_path_sum
,并传入根节点root
。 - 返回全局最大路径和:遍历完成后,我们返回全局最大路径和。
这个算法的时间复杂度是 O(n),其中 n 是二叉树中的节点数,因为我们需要访问每个节点一次。空间复杂度是 O(h),其中 h 是树的高度,在最坏的情况下,树退化成链表,空间复杂度为 O(n)。
给你一个整数数组 nums
,其中元素已经按 升序 排列,请你将其转换为一棵平衡二叉搜索树。
示例 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]
解题思路和步骤:
- 初始化结果列表:首先,我们创建一个空列表
result
,用于存储中序遍历的结果。 - 创建辅助函数:定义一个辅助函数
inorder
,它接受一个节点作为参数,并执行中序遍历。 - 递归执行中序遍历:在辅助函数中,我们首先检查当前节点是否为
None
,如果是,则返回。否则,我们递归地遍历左子树,然后访问当前节点,最后递归地遍历右子树。 - 调用辅助函数开始遍历:在主函数中,我们调用辅助函数
inorder
,并传入根节点root
。 - 返回结果列表:遍历完成后,我们返回
result
列表。
这个算法的时间复杂度是 O(n),其中 n 是二叉树中的节点数,因为我们需要访问每个节点一次。空间复杂度是 O(h),其中 h 是树的高度,在最坏的情况下,树退化成链表,空间复杂度为 O(n)。