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

1. 问题描述：

您需要在二叉树的每一行中找到最大的值。

示例：

输入: 

          1
         / \
        3   2
       / \     \  
      5 3    9 

输出: [1, 3, 9]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-largest-value-in-each-tree-row

2. 思路分析：

关于二叉树的相关题目都是可以使用递归来解决的，我们可以在递归的时候遍历整棵二叉树然后根据题目的要求处理即可，对于二叉树的题目比较习惯使用dfs解决，对于这道题目来说因为需要记录每一层的最大值，所以我们在dfs的时候维持一个深度即可，具体的做法是可以在递归方法中传递一个int类型的参数来记录当前节点的深度，当往下递归的时候深度为当前节点的深度加1，因为使用的是python年语言所以我们需要使用列表来记录每一层的深度，一开始的时候列表为空，在递归的时候判断当前列表的长度是否大于了层数，如果大于了说明之前递归的时候已经存在这一层了，所以比较当前层节点的值与对应的深度值取一个较大值即可，小于等于在列表末尾追加当前节点值即可，然后继续递归左子树与右子树，在递归的出口进行比较这样每递归一个节点就会比较得到对应的最大值

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, depth: int, res: List[int]):
        if not root: return
        # 说明之前递归的时候已经存在当前的深度了，所以需要取较大值
        if depth < len(res):
            res[depth] = max(res[depth], root.val)
        else:
            res.append(root.val)
        self.dfs(root.left, depth + 1, res)
        self.dfs(root.right, depth + 1, res)

    def largestValues(self, root: TreeNode) -> List[int]:
        res = list()
        self.dfs(root, 0, res)
        return res

if __name__ == '__main__':
    root = TreeNode(1)
    l = TreeNode(3)
    r = TreeNode(2)
    ll = TreeNode(5)
    lr = TreeNode(3)
    rr = TreeNode(9)
    root.left = l
    root.right = r
    l.left = ll
    l.right = lr
    r.right = rr
    print(Solution().largestValues(root))

 

本文地址：https://blog.csdn.net/qq_39445165/article/details/114002346