LeetCode-124:Binary Tree Maximum Path Sum

迷南。 2022-05-15 08:08 139阅读 0赞

题目

70

  • 很高兴leetcode上点击量最高的解法和我一样,而且这题难度也就Medium吧
  • 我真是提交了n多遍才理解了这题什么意思:在二叉树中,从一个节点开始,左右可以向下延伸,但不能分叉,可以说呈倒V字形,这样一个结构,这个结构可以从任何点开始,可以不包括root,可以只有一个节点,可以没有左分支或者右分支,计算出上边结构的所有节点val的和,要求找出一个结构,使得和最大

思路

  • 先对节点做一个认识:一个节点如果在一个这样的倒V字形结构中,那么就有两种情况
  • 第一,此节点就是这个结构的根节点,那么此时该结构的和就是sum=val+left+right,当然,如果left或者right小于0的话就不加了
  • 第二,此节点不是根节点,那么他需要提供一个最大的和给他的父节点,这个和可能是val,可能是val+left,可能是val+right,但不会是val+left+right,因为左右分支不能分叉
  • 程序整体的结构已经很明显了,是一个二叉树的后续遍历,两点需要注意,使用参数或者全局变量max来记录出现的所有倒V字形结构的sum中的最大值,这个值是最后需要返回的结果,再用返回值返回上边列举的第二种情况的值,提供给父节点使用
  • 好像就这么简单,实现起来也很简单,下边是leetcode上一个挺精简的解法,最下边是我自己的代码

    public class Solution {

    1. int maxValue;
    2. public int maxPathSum(TreeNode root) {
    3. maxValue = Integer.MIN_VALUE;
    4. maxPathDown(root);
    5. return maxValue;
    6. }
    7. private int maxPathDown(TreeNode node) {
    8. if (node == null) return 0;
    9. int left = Math.max(0, maxPathDown(node.left));
    10. int right = Math.max(0, maxPathDown(node.right));
    11. maxValue = Math.max(maxValue, left + right + node.val);
    12. return Math.max(left, right) + node.val;
    13. }

    }

代码

  1. public int maxPathSum(TreeNode root) {
  2. List<Integer> max = new ArrayList<>();
  3. max.add(-Integer.MAX_VALUE);
  4. findMax(root, max);
  5. return max.get(0);
  6. }
  7. public static int findMax(TreeNode root, List<Integer> max) {
  8. int ret = root.val;
  9. int left = -1;
  10. int right = -1;
  11. if (root.left != null) {
  12. left = findMax(root.left, max);
  13. }
  14. if (root.right != null) {
  15. right = findMax(root.right, max);
  16. }
  17. int tmp = ret + (left > 0 ? left : 0) + (right > 0 ? right : 0);
  18. if (tmp > max.get(0))
  19. max.set(0, tmp);
  20. if (left > 0 || right > 0) {
  21. ret += left > right ? left : right;
  22. }
  23. return ret;
  24. }

发表评论

表情:
评论列表 (有 0 条评论,139人围观)

还没有评论,来说两句吧...

相关阅读