Loading...
Given the root of a binary tree with a non-negative value on every node, choose a set of nodes such that no chosen node is the parent of another chosen node, and the sum of the chosen values is as large as possible.
Return that maximum sum.
Your function receives root as a TreeNode; the node type is provided for you, with val, left and right fields.
The examples below write the tree as its level-order traversal, where null marks a missing child of a listed node and trailing nulls are omitted. That is only how the input is displayed; the decoding is done for you.
Node.val ≤104Choose the root (3), the left subtree's leaf (3), and the right subtree's leaf (1): 3 + 3 + 1 = 7. No chosen node is another's parent.
Choose the two children of the root, 4 and 5: 4 + 5 = 9. Choosing the root instead would forbid both of them.
Click "Run" to test with sample cases or "Submit" to run all tests.