Maximum Non-Adjacent Path Sum in Binary Tree
Given the root of a binary tree represented as a level-order array, find the maximum sum of a non-empty subset of non-adjacent node values along any root-to-leaf path.
A root-to-leaf path is a sequence of nodes starting at the root node and descending to a leaf node. Two nodes along a root-to-leaf path are considered adjacent if one is the immediate parent of the other. You must choose a non-empty subset of nodes along a single root-to-leaf path such that no two selected nodes are adjacent along that path, and return the maximum achievable sum of node values.
[ "[3, 2, 3, null, 3, null, 1]" ]
Explanation. The root-to-leaf path [3, 2, 3] allows selecting the root node (3) and the leaf node (3). Since they are not adjacent along the path, their sum is 3 + 3 = 6.
[ "[-10, 5, -3]" ]
Explanation. The paths are [-10, 5] and [-10, -3]. The maximum non-empty non-adjacent subset sum is achieved by selecting just the node with value 5.
[ "[1, 2, 3, null, 4, 5, null]" ]
Explanation. The path [1, 3, 5] allows selecting nodes 1 and 5, which are non-adjacent along the path, giving a sum of 1 + 5 = 6.
[ "[10, -2, 7, 8, -5, null, 3]" ]
Explanation. The path [10, -2, 8] allows selecting nodes 10 and 8, which are non-adjacent along the path, giving a maximum sum of 10 + 8 = 18.
[ "[-5]" ]
Explanation. The tree consists of a single node with value -5. The only non-empty subset contains this single node.
[ "[5, 1, 2, 10, null, null, 20]" ]
Explanation. The path [5, 2, 20] allows selecting nodes 5 and 20 (non-adjacent along the path), yielding a sum of 5 + 20 = 25.
Follow-up: Can you compute the answer in O(N) time and O(H) auxiliary space, where N is the total number of nodes and H is the height of the tree?
The number of nodes in the binary tree is between 1 and 10^4. Each node value is an integer between -10^5 and 10^5. The input is provided as a stringified JSON array representing the level-order traversal of the tree, where missing nodes are denoted by null.