30daychallege (29) | Binary Tree Maximum Path Sum

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

For this problem, a path is defined as any sequence of nodes 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: [1,2,3]

       1
      / \
     2   3

Output: 6

Example 2:

Input: [-10,9,20,null,null,15,7]

   -10
   / \
  9  20
    /  \
   15   7

Output: 42

Đứng tại một nút nào đó, có 2 trường hợp xảy ra là root + left + right > max và root + max(left,right) sau này hoặc hiện tại sẽ lớn hơn max. Căn cứ vào đó ta duyệt DFS để tìm ra.

Thấy cái hình này khá dễ hiểu trên Medium:

Đây là code trên Java, lâu rồi không biết C/C++, giờ cảm giác quay lại với nó mệt thật, lâu hơn nữa là không viết trên Pascal, dù từng được giải cao với nó. Khi mình học một ngôn ngữ mới thì mình lại gần như quên hết các ngôn ngữ cũ. Nhưng khi vọng khi cần quay lại, vẫn phát huy được phần nào sức mạnh của những ngôn ngữ đó. 

Hết rồi, hẹn gặp lại các bạn vào ngày mai ! Cảm ơn bạn !