Binary tree maximum path sum

Dynamic Programming Tree Depth-First Search Binary Tree

42.0% acceptance

Feb 27, 2026

18340

785

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.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

// 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 {
  pub fn max_path_sum(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
    let mut max_sum = i32::MIN;
    Self::max_path_dfs(&root, &mut max_sum);
    max_sum
  }
  
  fn max_path_dfs(node: &Option<Rc<RefCell<TreeNode>>>, max_sum: &mut i32) -> i32 {
    if let Some(n) = node {
      let n = n.borrow();
      let left = Self::max_path_dfs(&n.left, max_sum).max(0);
      let right = Self::max_path_dfs(&n.right, max_sum).max(0);
      
      *max_sum = (*max_sum).max(n.val + left + right);
      
      n.val + left.max(right)
    } else {
      0
    }
  }
}