题解 | #每条路径的最大值#

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @return int整型一维数组
     */
    public static ArrayList<Integer> arrayList = new ArrayList<>();
    public int[] findMaxValues (TreeNode root) {
        search(root, Integer.MIN_VALUE);
        int [] result = new int [arrayList.size()];
        for (int i = 0; i < arrayList.size(); i++) {
            result[i] = arrayList.get(i);
        }
        return result;
    }
    public void search(TreeNode treeNode, int maxNumber) {
        if (treeNode == null) {
            return;
        }
        maxNumber = Math.max(treeNode.val, maxNumber);
	  // 如果左右节点都为null,说明已经到了一个路径的末尾，此时可以将maxNumber添加到集合
        if (treeNode.left == null && treeNode.right == null) {
            arrayList.add(maxNumber);
        }

        search(treeNode.left, maxNumber);
        search(treeNode.right, maxNumber);
    }
}

本题知识点分析：

1.二叉树的前序遍历

2.集合存取

3.集合转数组

4.递归

5.DFS深度优先搜索

6.API函数Math.max

本题解题思路分析：

1.创建全局变量arraylist存储每条路径上的最大数字

2.题干说路径从左往右的顺序返回这些最大值，因此要采用前序遍历，根左右，这样的顺序遍历

3.search函数用来寻找每条路径的最大值，要判断节点是否为null,就是返回条件

4.如果左右节点都为null,说明已经到了一个路径的末尾，此时可以将maxNumber添加到集合

5.分别递归左子树和右子树，就是前序遍历

本题使用编程语言：Java

如果你觉得本篇文章对你有帮助的话，可以点个赞支持一下，感谢~