You've successfully subscribed to The Daily Awesome
Great! Next, complete checkout for full access to The Daily Awesome
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.
Success! Your billing info is updated.
Billing info update failed.

124. 二叉树中的最大路径和 - Binary Tree Maximum Path Sum

. 1 min read

124. 二叉树中的最大路径和 - Binary Tree Maximum Path Sum

【后序遍历】 【动态规划】

给定一个非空二叉树,返回其最大路径和。

本题中,路径被定义为一条从树中任意节点出发,达到任意节点的序列。该路径至少包含一个节点,且不一定经过根节点。

Example:

示例 1:

输入: [1,2,3]

       1
      / \
     2   3

输出: 6

示例 2:

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

   -10
   / \
  9  20
    /  \
   15   7

输出: 42

Solutions

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

Solution 【后序遍历】 【动态规划】 ( 3ms)

class Solution {
    private int result = Integer.MIN_VALUE; 
        
    public int maxPathSum(TreeNode root) {
        getMax(root);
        return result;
    }
    
    /* postOrderTranversal */
    private int getMax(TreeNode r) {
        if(r == null) return 0;
        /* 并不是两个叶节点的距离 */
        /* 如果子树路径和为负则应当置0表示最大路径不包含子树 */
        int left = Math.max(0, getMax(r.left));         
        int right = Math.max(0, getMax(r.right));
        /* 判断在该节点包含左右子树的路径和是否大于当前最大路径和*/
        result = Math.max(result, r.val + left + right); 
        return Math.max(left, right) + r.val;
    }
}

Solution  ( 1ms)

class Solution {
   
    int ans;

    public int maxPathSum(TreeNode root) {
        ans = Integer.MIN_VALUE;
        maxDeep(root);
        return ans;
    }

    public int maxDeep(TreeNode root) {
        if (root == null) return 0;
        //叶子结点
        if (root.left == null && root.right == null) {
            ans = Math.max(ans, root.val);
            return root.val;
        } else {
            int left = maxDeep(root.left);
            int right = maxDeep(root.right);
            int tmp = Math.max(left, right )+ root.val; //当前节点到其子节点的最长路径
            tmp = Math.max(tmp, root.val); //是否可以不经过其子节点
            ans = Math.max(ans, tmp); 
            ans = Math.max(ans, left+right+root.val);
            return tmp;
        }
    }

}

Notes