124. Max path sum

124_solution1.c

#include "tree_node.h"
#include <limits.h>

static int max(int a, int b) { return a > b ? a : b; }

static int dfs(struct TreeNode *root, int *mx) {
  if (!root)
    return 0;

  int l = max(0, dfs(root->left, mx));
  int r = max(0, dfs(root->right, mx));

  *mx = max(*mx, l + r + root->val);
  return max(l, r) + root->val;
}

int maxPathSum(struct TreeNode *root) {
  int mx = INT_MIN;
  dfs(root, &mx);
  return mx;
}

tree_node.h

#pragma once

#include <stddef.h>

// Definition for a binary tree node.
struct TreeNode {
  int val;
  struct TreeNode *left;
  struct TreeNode *right;
};

124_solution1.cpp

#include "tree_node.h"
#include <algorithm>
#include <climits>

using namespace std;

class Solution {
public:
  int maxPathSum(TreeNode *root) {
    int mx = INT_MIN;
    dfs(root, mx);
    return mx;
  }

  int dfs(TreeNode *root, int &mx) {
    if (!root)
      return 0;

    int l = max(0, dfs(root->left, mx));
    int r = max(0, dfs(root->right, mx));

    mx = max(mx, l + r + root->val);
    return max(l, r) + root->val;
  }
};

tree_node.h

#pragma once

// Definition for a binary tree node.
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right)
      : val(x), left(left), right(right) {}
};

124_solution1.go

package trees

import "math"

func maxPathSum(root *TreeNode) int {
    mx := math.MinInt

    var dfs func(node *TreeNode) int
    dfs = func(node *TreeNode) int {
        if node == nil {
            return 0
        }

        l := max(0, dfs(node.Left))
        r := max(0, dfs(node.Right))

        mx = max(mx, l+r+node.Val)
        return max(l, r) + node.Val
    }

    dfs(root)
    return mx
}

tree_node.go

package trees

// Definition for a binary tree node.
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

124_solution1.java

class Solution {
    private int mx;

    public int maxPathSum(TreeNode root) {
        mx = Integer.MIN_VALUE;
        dfs(root);
        return mx;
    }

    private int dfs(TreeNode node) {
        if (node == null)
            return 0;

        int l = Math.max(0, dfs(node.left));
        int r = Math.max(0, dfs(node.right));

        mx = Math.max(mx, l + r + node.val);
        return Math.max(l, r) + node.val;
    }
}

TreeNode.java

// Definition for a binary tree node.
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;
    }
}

124_solution1.js

const TreeNode = require("./tree_node");

var maxPathSum = function (root) {
  let mx = -Infinity;

  const dfs = (node) => {
    if (!node) return 0;

    const l = Math.max(0, dfs(node.left));
    const r = Math.max(0, dfs(node.right));

    mx = Math.max(mx, l + r + node.val);
    return Math.max(l, r) + node.val;
  };

  dfs(root);
  return mx;
};

tree_node.js

// 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;
}

module.exports = TreeNode;

124_solution1.py

from typing import Optional

from tree_node import TreeNode


class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        mx = float("-inf")

        def dfs(node: Optional[TreeNode]) -> int:
            nonlocal mx
            if not node:
                return 0

            l = max(0, dfs(node.left))
            r = max(0, dfs(node.right))

            mx = max(mx, l + r + node.val)
            return max(l, r) + node.val

        dfs(root)
        return mx

tree_node.py

# 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

124_solution1.rs

use std::cell::RefCell;
use std::rc::Rc;

use crate::tree_node::TreeNode;

type Link = Option<Rc<RefCell<TreeNode>>>;

impl Solution {
    pub fn max_path_sum(root: Link) -> i32 {
        let mut mx = i32::MIN;
        Self::dfs(&root, &mut mx);
        mx
    }

    fn dfs(node: &Link, mx: &mut i32) -> i32 {
        let Some(n) = node else { return 0 };
        let n = n.borrow();

        let l = Self::dfs(&n.left, mx).max(0);
        let r = Self::dfs(&n.right, mx).max(0);

        *mx = (*mx).max(l + r + n.val);
        l.max(r) + n.val
    }
}

tree_node.rs

use std::cell::RefCell;
use std::rc::Rc;

// 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,
        }
    }
}