515 在每个树行中找最大值（dfs）

电玩女神 2022-08-30 01:57 125阅读 0赞

**1. 问题描述：**

给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。

**示例1：**

输入: root = \[1,3,2,5,3,null,9\]  
输出: \[1,3,9\]  
解释:  
1  
/ \\  
3 2  
/ \\ \\  
5 3 9

**示例2：**

输入: root = \[1,2,3\]  
输出: \[1,3\]  
解释:  
1  
/ \\  
2 3

**示例3：**

输入: root = \[1\]  
输出: \[1\]

**示例4：**

输入: root = \[1,null,2\]  
输出: \[1,2\]  
解释:  
1  
\\  
2

**示例5：**

输入: root = \[\]  
输出: \[\]  
提示：  
二叉树的节点个数的范围是 \[0,10 ^ 4\]  
\-2 ^ 31 <= Node.val <= 2 ^ 31 - 1  
来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/find-largest-value-in-each-tree-row

**2. 思路分析：**

分析题目可以知道我们可以使用**深搜**或者**宽搜**解决，下面使用的是深搜的方法，因为需要知道每一行的最大值，所以我们在递归方法中需要维护当前节点的深度d，声明一个全局变量maxD来记录当前的最大深度，当我们递归到每一层的时候依次更新最大深度maxD和每一层深度节点的最大值，因为一开始不知道节点的深度所以我们需要使用一个哈希表来维护每一层深度节点的最大值，最后遍历一下哈希表记将哈希表中每一层节点的最大值插入到答案中即可。

**3. 代码如下：**

from typing import List
    
    
    class TreeNode:
        def __init__(self, val=0, left=None, right=None):
            self.val = val
            self.left = left
            self.right = right
    
    
    class Solution:
        def dfs(self, root: TreeNode, d: int, dic: dict):
            if not root: return
            # 更新最大深度
            self.maxD = max(self.maxD, d)
            # 哈希表中没有值的时候那么为当前节点的值
            if d not in dic:
                dic[d] = root.val
            else:
                # 哈希表中有值的时候那么更新最大值
                dic[d] = max(dic[d], root.val)
            self.dfs(root.left, d + 1, dic)
            self.dfs(root.right, d + 1, dic)
        # 维护最大深度
        maxD = 0
    
        def largestValues(self, root: TreeNode) -> List[int]:
            res = list()
            # 使用哈希表记录每一层的最大值, 键为层数, 值为当前这一层的最大值
            dic = dict()
            self.dfs(root, 1, dic)
            for i in range(1, self.maxD + 1):
                res.append(dic[i])
            return res