Question

Formatted question description: https://leetcode.ca/all/124.html

A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root.

The path sum of a path is the sum of the node's values in the path.

Given the root of a binary tree, return the maximum path sum of any non-empty path.

Example 1:

Input: root = [1,2,3]
Output: 6
Explanation: The optimal path is 2 -> 1 -> 3 with a path sum of 2 + 1 + 3 = 6.

Example 2:

Input: root = [-10,9,20,null,null,15,7]
Output: 42
Explanation: The optimal path is 15 -> 20 -> 7 with a path sum of 15 + 20 + 7 = 42.

Constraints:

The number of nodes in the tree is in the range [1, 3 * 10⁴].
-1000 <= Node.val <= 1000

Algorithm

In the recursive function, if the current node does not exist, it directly returns 0.

Otherwise, call the recursive function on its left and right child nodes respectively. Since the path sum may be negative, and it is not supposed to add a negative path sum, so compared with 0, choose the larger one and add a positive number.

Then to update the global maximum result res, which is the sum of the maximum path ending at the left child node plus the sum of the maximum path ending at the right child node, plus the current node value, which is a complete path.

The return value is the larger value of left and right plus the value of the current node. Because the return value is defined as the sum of the path ending at the current node, only the larger value of left or right can be used. Not both.

Notes

The key is to judge well, the maximum value is 4 situations in total

left + root + right
left + root
right + root
root

It is to judge which is negative, if left and right child is negative, then discard it to 0 Compare with max

left+right+root,
Still root,
Or root+left,
Or root+right

The final return is

Look at root,
Or root+left,
Or root+right

Note that the max comparison is to add up both left and right, but when returning, it can only be either the left or the right

Code

public class Binary_Tree_Maximum_Path_Sum {

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


	public class Solution {
	    int max = Integer.MIN_VALUE;

	    public int maxPathSum(TreeNode root) {

	        // the path does not have to include root, but this max path sub-tree must have a sub-root
	        // eg: [1,-2,-3,1,3,-2,null,-1]

	        if (root == null) {
	            return 0;
	        }

	        traverse(root);

	        return max;
	    }

	    private int traverse(TreeNode root) {

	        if (root == null) {
	            return 0;
	        }

	        /*
	            1. root itself only
	            2. root + left-child
	            3. root + right-child
	            4. root + left-child + right-child
	        */

	        int leftChild = traverse(root.left);
	        int rightChild = traverse(root.right);

	        int localMax = Math.max(Math.max(root.val, root.val + leftChild), Math.max(root.val + rightChild, root.val + leftChild + rightChild));

	        // System.out.println("root: " + root.val + ", localMax: " + localMax);

	        max = Math.max(max, localMax);

	        return Math.max(root.val, Math.max(root.val + rightChild, root.val + leftChild));
	    }

	}

}

############

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private int ans = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        dfs(root);
        return ans;
    }

    private int dfs(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int left = Math.max(0, dfs(node.left));
        int right = Math.max(0, dfs(node.right));
        ans = Math.max(ans, node.val + left + right);
        return node.val + Math.max(left, right);
    }
}

// OJ: https://leetcode.com/problems/binary-tree-maximum-path-sum/
// Time: O(N)
// Space: O(H)
class Solution {
    int ans = INT_MIN;
    int dfs(TreeNode *root) {
        if (!root) return 0;
        int left = dfs(root->left), right = dfs(root->right);
        ans = max(ans, root->val + left + right);
        return max(0, root->val + max(left, right));
    }
public:
    int maxPathSum(TreeNode* root) {
        dfs(root);
        return ans;
    }
};

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxPathSum(self, root: TreeNode) -> int:
        ans = -inf

        def dfs(node: TreeNode) -> int:
            if not node:
                return 0
            left = max(0, dfs(node.left))
            right = max(0, dfs(node.right))
            nonlocal ans
            ans = max(ans, node.val + left + right)
            return node.val + max(left, right)

        dfs(root)
        return ans

############

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
  def maxPathSum(self, root):
    """
    :type root: TreeNode
    :rtype: int
    """

    def dfs(root):
      if not root: return (0, float("-inf"))
      (l, lm), (r, rm) = map(dfs, [root.left, root.right])
      return (max(root.val, root.val + max(l, r)), max(lm, rm, root.val + max(l, r), root.val, root.val + l + r))

    return dfs(root)[1]

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func maxPathSum(root *TreeNode) int {
	ans := math.MinInt32

	var dfs func(*TreeNode) int
	dfs = func(node *TreeNode) int {
		if node == nil {
			return 0
		}
		left := max(0, dfs(node.Left))
		right := max(0, dfs(node.Right))
		ans = max(ans, node.Val+left+right)
		return node.Val + max(left, right)
	}

	dfs(root)
	return ans
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxPathSum = function (root) {
    let ans = -1000;
    let dfs = function (root) {
        if (!root) {
            return 0;
        }
        const left = Math.max(0, dfs(root.left));
        const right = Math.max(0, dfs(root.right));
        ans = Math.max(ans, left + right + root.val);
        return root.val + Math.max(left, right);
    };
    dfs(root);
    return ans;
};

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    private int ans;

    public int MaxPathSum(TreeNode root) {
        ans = int.MinValue;
        dfs(root);
        return ans;
    }

    private int dfs(TreeNode root)
    {
        if (root == null) return 0;
        int left = Math.Max(0, dfs(root.left));
        int right = Math.Max(0, dfs(root.right));
        ans = Math.Max(ans, left + right + root.val);
        return root.val + Math.Max(left, right);
    }
}

// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
    fn dfs(root: &Option<Rc<RefCell<TreeNode>>>, res: &mut i32) -> i32 {
        if root.is_none() {
            return 0;
        }
        let node = root.as_ref().unwrap().borrow();
        let left = 0.max(Self::dfs(&node.left, res));
        let right = 0.max(Self::dfs(&node.right, res));
        *res = (node.val + left + right).max(*res);
        node.val + left.max(right)
    }

    pub fn max_path_sum(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        let mut res = -1000;
        Self::dfs(&root, &mut res);
        res
    }
}

124 - Binary Tree Maximum Path Sum

Question

Algorithm

Notes

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Notes

Code

All Problems

All Solutions