leetcode124. 二叉树中的最大路径和

leetcode124. 二叉树中的最大路径和

六月 26, 2020

leetcode124. 二叉树中的最大路径和

给定一个非空二叉树，返回其最大路径和。
本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。

示例 1:
输入: [1,2,3]

  1
 / \
2   3

输出: 6

示例 2:

输入: [-10,9,20,null,null,15,7]

 -10
 / \
9  20
  /  \
 15   7

输出: 42

递归

理解了递归的原理，就可以很快写出这种题。
自底向上。考虑某个子树，他的子节点是n，当前最大的路径只有四种情况：

  • n+left
  • n+right
  • n
  • n+left+right
    递归函数返回最大值 ，注意最后一个值不能返回，因为不能和上面一个节点构成路径。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    class Solution {
        private int max = Integer.MIN_VALUE;
        public int maxPathSum(TreeNode root) {
            dfs(root);
            return max;
        }
        public int dfs(TreeNode root) {
            //返回当前子树的最大值
            if (root == null) return 0;
            int left = dfs(root.left);
            int right = dfs(root.right);
            //当前节点为n,对于当前节点来说，最大值可以为n+left,n+right,n,n+left+right
            //上面四项中的一个，但是返回是不能返回第四个的，那种路径是不成立的
            int p = Math.max(root.val,Math.max(root.val+left,root.val+right));
            max = Math.max(max,p);
            int p2 = Math.max(p,root.val+left+right);
            max = Math.max(max,p2);
            return p;
        }
    }
    leetcode 113