# Binary Tree Maximum Path Sum

Hard — Leetcode problem

Given a **non-empty** binary tree, find the maximum path sum.

For this problem, a path is defined as any node sequence from some starting node to any node in the tree along the parent-child connections. The path must contain **at least one node** and does not need to go through the root.

**Example 1:**

**Input:** root = [1,2,3]

**Output:** 6

**Example 2:**