[LeetCode 124. Binary Tree Maximum Path Sum(Hard)] JavaScript Recursion Solution

LeetCode 124. Binary Tree Maximum Path Sum (Hard)

題目：

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 path.

理解：

找出 binary tree 中所有可能的直線路徑的 sum 的最大值

想法：

聯想到 graph 的概念和 Fibonacci sequence 的 recursion 解法 ，從 root 開始，一直往 left 和 right node 遞迴，算出有多少 path 的組合會到達其中一個 node，再把這些排列組合和 node 本身的值相加，base case 是如果 node 不存在就回傳 [] 或是 left 和 right node 都不存在就回傳 [node.val]

First Submission (Implemented by myself)

時間：一小時

虛擬碼：

Find all the combination of paths to the current node, including the left and the right path
loop through left and right path respectively
    add node.val and push to previousPath array and allPathSum array
loop through left and right path (nested for loop)
    add node.val and push to allPathSum array
After traversing all nodes, loop through allPathSum to find the max value

實作：

結果：

Success

Runtime: 1340 ms (faster than 5.27% of JavaScript submission)
Memory Usage: 64.8 MB (less than 5.18% of JavaScript submissions)

雖然成功解出，但時間和空間複雜度都很差，正在思考優化解

Second Submission (Refer to Solution)

參考解答後發現不用像前一個解法一樣把 leftPath/rightPath 都用 array 存起來，直接存最大值，如果是負數則換成 0 就好。

實作：

Time complexity: O(N), because we need to loop through every node.

Space complexity: O(H), H is tree height to keep the recursion stack.