第一题、77.组合

方法一、递归实现组合型枚举
补充知识：用递归实现二进制枚举（子集枚举），找到一个长度为 n 的序列 a 的所有子序列。代码如下：

temp = []  # 初始化临时列表，用于存储当前组合

def dfs(cur, n):
    if cur == n + 1:  # 如果当前值超过了 n，说明已经处理完所有元素
        # 记录答案
        # 在这里可以处理或保存当前的组合，例如：
        # result.append(list(temp))
        return  # 递归结束条件
    
    # 考虑选择当前位置
    temp.append(cur)  # 将当前元素添加到组合中
    dfs(cur + 1, n)  # 递归处理下一个元素
    temp.pop()  # 回溯，撤销选择当前元素
    
    # 考虑不选择当前位置
    dfs(cur + 1, n)  # 递归处理下一个元素，当前元素不加入组合中

上面的代码中使用深度优先搜索dfs来生成所有从1到n的子集，dfs(cur, n) 参数表示当前位置是 cur，原序列总长度为 n。原序列的每个位置在答案序列中的状态有被选中和不被选中两种，用 temp 数组存放已经被选出的数字。在进入 dfs(cur, n) 之前 [1, cur − 1] 位置的状态是确定的，而 [cur, n] 内位置的状态是不确定的，dfs(cur, n) 需要确定 cur 位置的状态，然后求解子问题 dfs(cur + 1, n)。
对于 cur 位置，需要考虑 a[cur] 取或者不取。如果取，需要把 a[cur] 放入一个临时的答案数组中（即上面代码中的 temp），再执行 dfs(cur + 1, n)，执行结束后需要对 temp 进行回溯；如果不取，则直接执行 dfs(cur + 1, n)。在整个递归调用的过程中，cur 是从小到大递增的，当 cur 增加到 n + 1 的时候，记录答案并终止递归。二进制枚举的时间复杂度是 O(2^n)。
组合枚举的代码框架借鉴二进制枚举。在 n 个元素选 k 个，在 dfs 的时候需要多传入一个参数 k，即 dfs(cur, n, k)。在每次进入这个 dfs 函数时，判断当前 temp 的长度是否为 k，如果为 k，就把 temp 加入答案并直接返回。即：

def dfs(cur, n, k, temp):
    if len(temp) == k:
        result.append(temp[:])
        return
    if cur > n:
        return
    # 取当前位置的元素
    temp.append(cur)
    dfs(cur + 1, n, k)
    temp.pop()  # 回溯
    # 不取当前位置的元素
    dfs(cur + 1, n, k)

☆☆☆剪枝，如果当前 temp 的大小为 s，未确定状态的区间 [cur,n] 的长度为 t，如果 s+t<k，那么即使 t 个都被选中，也不可能构造出一个长度为 k 的序列，故这种情况就没有必要继续向下递归，即可以在每次递归开始的时候做一次这样的判断：

if len(temp) + (n - cur + 1) < k:
    return

那么代码如下：

def dfs(cur, n, k, temp, result):
    # 剪枝：temp 长度加上区间 [cur, n] 的长度小于 k，不可能构造出长度为 k 的 temp
    if len(temp) + (n - cur + 1) < k:
        return
    
    # 记录合法的答案
    if len(temp) == k:
        result.append(temp[:])
        return
    
    # cur == n + 1 的时候结束递归
    if cur > n: 
        return
    
    # 考虑选择当前位置
    temp.append(cur)
    dfs(cur + 1, n, k, temp, result)
    temp.pop()
    
    # 考虑不选择当前位置
    dfs(cur + 1, n, k, temp, result)

上述代码还可以进一步优化。上述代码中有三个 if 判断，第三处的 if 可以删除。因为：
首先，cur=n+1 的时候，一定不可能出现 s>k（s 是前文中定义的 temp 的大小），因为自始至终 s 绝不可能大于 k，它等于 k 的时候就会被第二处 if 记录答案并返回；
如果 cur=n+1 的时候 s=k，它也会被第二处 if 记录答案并返回；
如果 cur=n+1 的时候 s<k，一定会在 cur<n+1 的某个位置的时候发现 s+t<k，它也会被第一处 if 剪枝。
因此，第三处 if 可以删除。最终代码如下：

class Solution(object):
    def __init__(self):
        self.temp = []  # 用于存储当前的组合
        self.ans = []   # 用于存储所有合法的组合

    def dfs(self, cur, n, k):
        # 剪枝：temp 长度加上区间 [cur, n] 的长度小于 k，不可能构造出长度为 k 的 temp
        if len(self.temp) + (n - cur + 1) < k:
            return
        
        # 记录合法的答案
        if len(self.temp) == k:
            self.ans.append(self.temp[:])
            return
        
        # 考虑选择当前位置
        self.temp.append(cur)
        self.dfs(cur + 1, n, k)  # 递归到下一个位置
        self.temp.pop()  # 撤销选择
        
        # 考虑不选择当前位置
        self.dfs(cur + 1, n, k)  # 递归到下一个位置

    def combine(self, n, k):
        self.dfs(1, n, k)  # 从位置 1 开始进行深度优先搜索
        return self.ans

用时和内存

时空复杂度

示例详解 n = 4 和 k = 2 ：（此模拟对我来说很有难度，感觉没太模明白。。）

• 初始时 temp = []，ans = []

1. 调用 combine(4, 2):
   • 进入 dfs(1, 4, 2)。
2. dfs(1, 4, 2):
   • 剪枝: len(temp) + (4 - 1 + 1) = 0 + 4 = 4，大于 2，不剪枝。
   • 记录合法的答案: len(temp) = 0，不等于 2，不记录答案。
   • 选择当前位置: temp = [1]。
     • 递归调用 dfs(2, 4, 2):
3. dfs(2, 4, 2):
   • 剪枝: len(temp) + (4 - 2 + 1) = 1 + 3 = 4，大于 2，不剪枝。
   • 记录合法的答案: len(temp) = 1，不等于 2，不记录答案。
   • 选择当前位置: temp = [1, 2]。
     • 递归调用 dfs(3, 4, 2):
4. dfs(3, 4, 2):
   • 剪枝: len(temp) + (4 - 3 + 1) = 2 + 2 = 4，大于 2，不剪枝。
   • 记录合法的答案: len(temp) = 2，等于 2，记录 temp = [1, 2] 到 ans，ans = [[1, 2]]。
   • 撤销选择: temp = [1]。
   • 不选择当前位置: 递归调用 dfs(3, 4, 2):
5. dfs(3, 4, 2):
   • 剪枝: len(temp) + (4 - 3 + 1) = 1 + 2 = 3，大于 2，不剪枝。
   • 记录合法的答案: len(temp) = 1，不等于 2，不记录答案。
   • 选择当前位置: temp = [1, 3]。
     • 递归调用 dfs(4, 4, 2):
6. dfs(4, 4, 2):
   • 剪枝: len(temp) + (4 - 4 + 1) = 2 + 1 = 3，大于 2，不剪枝。
   • 记录合法的答案: len(temp) = 2，等于 2，记录 temp = [1, 3] 到 ans，ans = [[1, 2], [1, 3]]。
   • 撤销选择: temp = [1]。
   • 不选择当前位置: 递归调用 dfs(4, 4, 2):
7. dfs(4, 4, 2):
   • 剪枝: len(temp) + (4 - 4 + 1) = 1 + 1 = 2，等于 2，不剪枝。
   • 记录合法的答案: len(temp) = 1，不等于 2，不记录答案。
   • 撤销选择: temp = []。
   • 不选择当前位置: 递归调用 dfs(2, 4, 2):
8. dfs(2, 4, 2):
   • 剪枝: len(temp) + (4 - 2 + 1) = 0 + 3 = 3，大于 2，不剪枝。
   • 记录合法的答案: len(temp) = 0，不等于 2，不记录答案。
   • 选择当前位置: temp = [2]。
     • 递归调用 dfs(3, 4, 2):
9. dfs(3, 4, 2):
   • 剪枝: len(temp) + (4 - 3 + 1) = 1 + 2 = 3，大于 2，不剪枝。
   • 记录合法的答案: len(temp) = 1，不等于 2，不记录答案。
   • 选择当前位置: temp = [2, 3]。
     • 递归调用 dfs(4, 4, 2):
10. dfs(4, 4, 2):
    • 剪枝: len(temp) + (4 - 4 + 1) = 2 + 1 = 3，大于 2，不剪枝。
    • 记录合法的答案: len(temp) = 2，等于 2，记录 temp = [2, 3] 到 ans，ans = [[1, 2], [1, 3], [1, 4], [2, 3]]。
    • 撤销选择: temp = [2]。
    • 不选择当前位置: 递归调用 dfs(4, 4, 2):
11. dfs(4, 4, 2):
    • 剪枝: len(temp) + (4 - 4 + 1) = 1 + 1 = 2，等于 2，不剪枝。
    • 记录合法的答案: len(temp) = 1，不等于 2，不记录答案。
    • 撤销选择: temp = []。
    • 不选择当前位置: 递归调用 dfs(3, 4, 2):
12. dfs(3, 4, 2):
    • 剪枝: len(temp) + (4 - 3 + 1) = 0 + 2 = 2，等于 2，不剪枝。
    • 记录合法的答案: len(temp) = 0，不等于 2，不记录答案。
    • 选择当前位置: temp = [3]。
      • **递归调用 dfs(4, 4, 2):
13. dfs(4, 4, 2):
    • 剪枝: len(temp) + (4 - 4 + 1) = 1 + 1 = 2，等于 2，不剪枝。
    • 记录合法的答案: len(temp) = 1，不等于 2，不记录答案。
    • 选择当前位置: temp = [3, 4]。
      • **递归调用 dfs(5, 4, 2):
14. dfs(5, 4, 2):
    • 剪枝: len(temp) + (4 - 5 + 1) = 2 + 0 = 2，等于 2，不剪枝。
    • 记录合法的答案: len(temp) = 2，等于 2，记录 temp = [3, 4] 到 ans，ans = [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]。
    • 撤销选择: temp = [3]。
    • 不选择当前位置: 递归调用 dfs(4, 4, 2):
15. dfs(4, 4, 2):
    • 剪枝: len(temp) + (4 - 4 + 1) = 1 + 1 = 2，等于 2，不剪枝。
    • 记录合法的答案: len(temp) = 1，不等于 2，不记录答案。
    • 撤销选择: temp = []。
    • 不选择当前位置: 递归调用 dfs(4, 4, 2):
16. dfs(4, 4, 2):
    • 剪枝: len(temp) + (4 - 4 + 1) = 0 + 1 = 1，小于 2，剪枝。
    • 结束递归。
      方法二：非递归（字典序法）实现组合型枚举
      太复杂，未学习。

第二题、78.子集

方法一、迭代法实现子集枚举
记原序列中元素的总数为 n。原序列中的每个数字 ai 的状态可能有两种，即「在子集中」和「不在子集中」。用 1 表示「在子集中」，0 表示不在子集中，那么每一个子集可以对应一个长度为 n 的 0/1 序列，第 i 位表示 ai 是否在子集中。例如，n=3 ，a={5,2,9} 时：

n=3，a={5,2,9}

可以发现 0/1 序列对应的二进制数正好从 0 到 2^n −1。所以可以枚举 mask∈[0, 2^n −1]，mask 的二进制表示是一个 0/1 序列，按照这个 0/1 序列在原集合当中取数。当枚举完所有 2^n 个 mask，就能构造出所有的子集。

class Solution(object):
    def __init__(self):
        self.t = []  # 用于存储当前的子集
        self.ans = []  # 用于存储所有的子集

    def subsets(self, nums):
        n = len(nums)  # 获取输入列表的长度
        for mask in range(1 << n):  # 遍历从 0 到 2^n - 1 的所有可能的掩码
            self.t = []  # 清空当前子集
            for i in range(n):  # 遍历 nums 中的每一个元素
                if mask & (1 << i):  # 检查第 i 位是否为 1
                    self.t.append(nums[i])  # 如果第 i 位为 1，则将 nums[i] 加入当前子集
            self.ans.append(self.t[:])  # 将当前子集加入到答案列表中
        return self.ans  # 返回所有的子集

用时和内存

时间复杂度：O(n×2^n)。一共 2^n 个状态，每种状态需要 O(n) 的时间来构造子集。
空间复杂度：O(n)。即构造子集使用的临时数组 t 的空间代价。

①在 Python 2 中，list 对象没有 copy 方法。使用切片操作 [:] 来代替 copy 方法。77和78题都有用到类似形式：

self.ans.append(self.temp[:])
self.ans.append(self.t[:])

②mask & (1 << i)？
& 是按位与操作符。它对两个数的每一位进行与运算：如果两个对应位都为 1，结果为 1，否则为 0。
<< 是左移操作符。它将一个数的二进制表示左移指定的位数，右边补 0。

方法二、递归法实现子集枚举
补充知识：同77题方法一

class Solution(object):
    def __init__(self):
        self.t = []  # 用于存储当前的子集
        self.ans = []  # 用于存储所有的子集

    def dfs(self, cur, nums):
        if cur == len(nums):  # 如果当前索引等于 nums 的长度，表示已经处理完所有元素
            self.ans.append(self.t[:])  # 将当前子集的副本加入到答案列表中
            return  # 结束当前递归
        self.t.append(nums[cur])  # 将 nums[cur] 加入当前子集
        self.dfs(cur + 1, nums)  # 递归处理下一个元素，考虑选择当前元素的情况
        self.t.pop()  # 撤销选择，回溯到上一个状态
        self.dfs(cur + 1, nums)  # 递归处理下一个元素，考虑不选择当前元素的情况

    def subsets(self, nums):
        self.dfs(0, nums)  # 从索引 0 开始进行深度优先搜索
        return self.ans  # 返回所有的子集

用时和内存

时间复杂度同上。
空间复杂度：O(n)。临时数组 t 的空间代价是 O(n)，递归时栈空间的代价为 O(n)。

第三题、50.Pow(x, n)

当指数 n 为负数时，可以计算 x^−n 再取倒数得到结果，因此只需要考虑 n 为自然数的情况。
方法一：快速幂 + 递归

思路

思路

class Solution(object):
    def myPow(self, x, n):
        def quickMul(N):
            if N == 0:
                return 1.0
            y = quickMul(N // 2)
            return y * y if N % 2 == 0 else y * y *x 

        return quickMul(n) if n >= 0 else 1.0 / quickMul(-n)

用时和内存

时间复杂度：O(logn)，即为递归的层数。
空间复杂度：O(logn)，即为递归的层数。这是由于递归的函数调用会使用栈空间。

方法二、快速幂 + 迭代

思路

思路

对此方法我只做了一个了解。。

class Solution(object):
    def myPow(self, x, n):
        def quickMul(N):
            ans = 1.0
            # 贡献的初始值为 x
            x_contribute = x
            # 在对 N 进行二进制拆分的同时计算答案
            while N > 0:
                if N % 2 == 1:
                    # 如果 N 二进制表示的最低位为 1，那么需要计入贡献
                    ans *= x_contribute
                # 将贡献不断地平方
                x_contribute *= x_contribute
                # 舍弃 N 二进制表示的最低位，这样我们每次只要判断最低位即可
                N //= 2
            return ans
        
        return quickMul(n) if n >= 0 else 1.0 / quickMul(-n)

用时和内存

时间复杂度：O(logn)，即为对 n 进行二进制拆分的时间复杂度。
空间复杂度：O(1)。

第四题、169.多数元素

方法一、暴力
枚举数组中的每个元素，再遍历一遍数组统计其出现次数。但该方法的时间复杂度是 O(n^2)，会超出时间限制。

方法二、哈希表
使用哈希映射（HashMap）来存储每个元素以及出现的次数。对于哈希映射中的每个键值对，键表示一个元素，值表示该元素出现的次数。
用一个循环遍历数组 nums 并将数组中的每个元素加入哈希映射中。在这之后，遍历哈希映射中的所有键值对，返回值最大的键。也可以在遍历数组 nums 时候使用打擂台的方法，维护最大的值，这样省去了最后对哈希映射的遍历。

class Solution(object):
    def majorityElement(self, nums):
        # 使用 Counter 统计 nums 中每个元素出现的次数
        counts = collections.Counter(nums)
        
        # 找出出现次数最多的元素并返回
        # max(counts.keys(), key=counts.get) 表示从 counts 的键中，
        # 找到对应值最大的键，即多数元素
        return max(counts.keys(), key=counts.get)

用时和内存

时空复杂度

import collections

# 创建一个 Counter 对象
nums = [1, 2, 2, 3, 3, 3, 4]
counts = collections.Counter(nums)

print(counts)

输出结果：

Counter({3: 3, 2: 2, 1: 1, 4: 1})

② max(counts.keys(), key=counts.get) ？
从 counts 字典的键中找到对应值最大的键，也就是找出出现次数最多的元素。
counts.keys():

• counts 是一个 Counter 对象，类似于字典。
• counts.keys() 返回 counts 中所有的键，也就是被统计的元素。
  key=counts.get:
• max() 函数接受一个可选的 key 参数，这个参数是一个函数，用于指定如何比较元素。
• counts.get 是一个函数，它会返回某个键在 counts 中对应的值，即该键的计数。
• 当 max() 在比较 counts 的键时，它会调用 counts.get 函数来获取每个键的计数，并使用这些计数进行比较。
  max(counts.keys(), key=counts.get):
• 这个表达式会遍历 counts 的所有键，并使用 counts.get 获取每个键的计数。
• 然后，max() 函数会找到计数最大的键，也就是出现次数最多的元素。
  假设 counts 是如下的 Counter 对象：

counts = collections.Counter({'a': 5, 'b': 3, 'c': 9})

那么，max(counts.keys(), key=counts.get) 的过程如下：

• 比较 'a' 的计数（5），'b' 的计数（3），和 'c' 的计数（9）。
• 返回 'c'，因为 'c' 的计数最大。
  最终结果是 'c'，即在字典 counts 中出现次数最多的键。

方法三、排序

思路

证明

class Solution(object):
    def majorityElement(self, nums):
        nums.sort()
        return nums[len(nums) // 2]

用时和内存

时间复杂度：O(nlogn)。将数组排序的时间复杂度为 O(nlogn)。
空间复杂度：O(logn)。如果使用语言自带的排序算法，需要使用 O(logn) 的栈空间。如果自己编写堆排序，则只需要使用 O(1) 的额外空间。

方法四、随机化（此方法了解即可）

思路和算法

class Solution(object):
    def majorityElement(self, nums):
        # 定义多数元素需要超过的次数，即数组长度的一半
        majority_count = len(nums) // 2
        
        while True:
            # 随机从 nums 列表中选择一个元素作为候选元素
            candidate = random.choice(nums)
            
            # 计算 candidate 在 nums 中出现的次数
            # 通过生成器表达式 sum(1 for elem in nums if elem == candidate)
            # 逐一检查 nums 中的每个元素，统计与 candidate 相等的元素数量
            if sum(1 for elem in nums if elem == candidate) > majority_count:
                # 如果 candidate 出现的次数超过 majority_count，则返回该元素
                return candidate

用时和内存

时间复杂度分析

空间复杂度：O(1)。随机方法只需要常数级别的额外空间。

方法五、分治

思路

算法

class Solution(object):
    def majorityElement(self, nums):
        def majority_element_rec(lo, hi):
            # 基本情况：如果数组大小为 1，则该元素就是多数元素
            if lo == hi:
                return nums[lo]

            # 对当前切片的左半部分和右半部分进行递归
            mid = (hi - lo) // 2 + lo  # 计算当前切片的中点
            left = majority_element_rec(lo, mid)  # 递归求解左半部分的多数元素
            right = majority_element_rec(mid + 1, hi)  # 递归求解右半部分的多数元素

            # 如果左半部分和右半部分的多数元素相同，则返回该元素
            if left == right:
                return left

            # 否则，计算左半部分和右半部分的多数元素在当前切片中的出现次数
            left_count = sum(1 for i in range(lo, hi + 1) if nums[i] == left)
            right_count = sum(1 for i in range(lo, hi + 1) if nums[i] == right)

            # 返回出现次数更多的元素
            return left if left_count > right_count else right

        # 从整个数组的范围递归求解多数元素
        return majority_element_rec(0, len(nums) - 1)

用时和内存

时空复杂度

方法六：Boyer-Moore 投票算法
如果把众数记为 +1，把其他数记为 −1，将它们全部加起来，显然和大于 0，从结果本身可以看出众数比其他数多。

算法

证明见官方题解（我选择放弃）

class Solution(object):
    def majorityElement(self, nums):
        count = 0  # 初始化计数器
        candidate = None  # 初始化候选元素

        for num in nums:
            if count == 0:
                # 当计数器为 0 时，更新候选元素为当前元素
                candidate = num
            # 如果当前元素等于候选元素，计数器加 1；否则，计数器减 1
            count += (1 if num == candidate else -1)

        return candidate  # 返回最终的候选元素

用时和内存

第五题、17. 电话号码的字母组合

题目描述

方法、回溯
首先使用哈希表存储每个数字对应的所有可能的字母，然后进行回溯操作。
回溯过程中维护一个字符串，表示已有的字母排列（如果未遍历完电话号码的所有数字，则已有的字母排列是不完整的）。该字符串初始为空。每次取电话号码的一位数字，从哈希表中获得该数字对应的所有可能的字母，并将其中的一个字母插入到已有的字母排列后面，然后继续处理电话号码的后一位数字，直到处理完电话号码中的所有数字，即得到一个完整的字母排列。然后进行回退操作，遍历其余的字母排列。
回溯算法用于寻找所有的可行解，如果发现一个解不可行，则会舍弃不可行的解。在这道题中，由于每个数字对应的每个字母都可能进入字母组合，因此不存在不可行的解，直接穷举所有的解即可。

class Solution(object):
    def letterCombinations(self, digits):
        # 如果输入的数字串为空，则返回空列表
        if not digits:
            return list()

        # 电话键盘映射表
        phoneMap = {
            "2": "abc",
            "3": "def",
            "4": "ghi",
            "5": "jkl",
            "6": "mno",
            "7": "pqrs",
            "8": "tuv",
            "9": "wxyz",
        }

        # 回溯函数
        def backtrack(index):
            # 终止条件：如果当前索引等于数字串的长度，则说明组合完成
            if index == len(digits):
                combinations.append("".join(combination))  # 将当前组合添加到结果列表
            else:
                # 获取当前数字对应的字母
                digit = digits[index]
                # 遍历当前数字对应的所有字母
                for letter in phoneMap[digit]:
                    combination.append(letter)  # 将字母添加到组合中
                    backtrack(index + 1)  # 递归处理下一个数字
                    combination.pop()  # 撤销选择，回溯到上一步
            
        combination = list()  # 存储当前的组合
        combinations = list()  # 存储所有的组合
        backtrack(0)  # 从索引0开始回溯
        return combinations  # 返回所有的组合

用时和内存

时空复杂度

回溯法总结：！！！！！！！！！

回溯法是一种解决组合、排列和子集问题的经典算法思想。它通过逐步构造解的过程，并在发现当前解无法满足条件时，回退到上一步，尝试其他可能的解。常见的题型包括排列问题、组合问题、子集问题、分割问题、图的着色问题等。
回溯法的基本思想

1. 选择：从当前状态出发，选择一个候选项。
2. 探索：对选择的候选项进行递归，继续向下探索。
3. 回退：当探索到某个状态无法满足条件时，撤销上一步选择，尝试其他候选项。
   回溯法的代码模板：

def backtrack(path, used, res, options):
    # 终止条件（可以根据具体问题设置）
    if len(path) == len(options):
        res.append(path[:])  # 保存当前路径的副本
        return

    for i in range(len(options)):
        if used[i]:
            continue
        
        # 做出选择
        path.append(options[i])
        used[i] = True
        
        # 递归探索
        backtrack(path, used, res, options)
        
        # 撤销选择
        path.pop()
        used[i] = False

def solve(options):
    res = []
    path = []
    used = [False] * len(options)
    backtrack(path, used, res, options)
    return res

常见的回溯法题型

1. 排列问题：给定一组数字，生成所有的排列。
   • 示例：全排列问题。
2. 组合问题：从给定的集合中选择部分元素，生成所有的组合。
   • 示例：组合总和、组合问题。
3. 子集问题：从给定的集合中生成所有可能的子集。
   • 示例：子集问题。
4. 分割问题：将一个集合分成多个子集，满足特定条件。
   • 示例：分割回文字符串问题。
5. 图的着色问题：给定图的顶点，使用最少的颜色对其进行着色，使得相邻的顶点颜色不同。
   • 示例：图的着色问题。

第六题、515. 在每个树行中找最大值

方法一、深度优先搜索
用树的「先序遍历」来进行「深度优先搜索」处理，并用 curHeight 来标记遍历到的当前节点的高度。当遍历到 curHeight 高度的节点就判断是否更新该层节点的最大值。

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def largestValues(self, root):
        ans = []  # 用于存储每层的最大值
        
        def dfs(node, curHeight):
            # 如果当前节点为空，则返回
            if node is None:
                return
            
            # 如果当前层的索引等于最大值列表的长度，说明这是新的一层
            if curHeight == len(ans):
                ans.append(node.val)  # 将当前节点的值作为当前层的最大值添加到最大值列表
            else:
                # 更新当前层的最大值
                ans[curHeight] = max(ans[curHeight], node.val)
            
            # 递归处理左子树
            dfs(node.left, curHeight + 1)
            # 递归处理右子树
            dfs(node.right, curHeight + 1)
        
        # 从根节点开始进行深度优先搜索
        dfs(root, 0)
        
        # 返回每层的最大值列表
        return ans

用时和内存

时间复杂度：O(n)，其中 n 为二叉树节点个数。二叉树的遍历中每个节点会被访问一次且只会被访问一次。
空间复杂度：O(height)。其中 height 表示二叉树的高度。递归函数需要栈空间，而栈空间取决于递归的深度，因此空间复杂度等价于二叉树的高度。

方法二、广度优先搜索
「广度优先搜索」中的队列里存放的是「当前层的所有节点」。每次拓展下一层的时候，不同于「广度优先搜索」的每次只从队列里拿出一个节点，把当前队列中的全部节点拿出来进行拓展，这样能保证每次拓展完的时候队列里存放的是下一层的所有节点，即是一层一层地进行拓展，然后每一层用 maxVal 来标记该层节点的最大值。当该层全部节点都处理完后，maxVal 就是该层全部节点中的最大值。

class Solution(object):
    def largestValues(self, root):
        if root is None:
            return []
        
        ans = []
        q = [root]  # 初始化队列，将根节点添加到队列中
        
        while q:
            maxVal = float('-inf')  # 初始化当前层的最大值为负无穷
            tmp = q  # 保存当前层的节点
            q = []  # 清空队列，准备存储下一层的节点
            
            for node in tmp:
                maxVal = max(maxVal, node.val)  # 更新当前层的最大值
                if node.left:
                    q.append(node.left)  # 如果左子节点存在，将其添加到队列中
                if node.right:
                    q.append(node.right)  # 如果右子节点存在，将其添加到队列中
            
            ans.append(maxVal)  # 将当前层的最大值添加到结果列表中
        
        return ans

用时和内存

时间复杂度：O(n)，其中 n 为二叉树节点个数，每一个节点仅会进出队列一次。
空间复杂度：O(n)，存储二叉树节点的空间开销。

总结广度优先搜索在树中的应用

一般当广度优先搜索应用于树的时候，思路都是在每次拓展下一层的时候，把当前队列中的全部节点拿出来进行拓展，这样能保证每次拓展完的时候队列里存放的是下一层的所有节点，即是一层一层地进行拓展。如题515、102、104。。。