Richest Search Tree Inside
You are given the root of a binary tree. A subtree is a node together with everything below it.
A subtree is a search tree when, for each of its nodes, all values in the left part are smaller than the node and all values in the right part are larger. Equal values are not allowed on either side.
Return the largest sum of values of a subtree that is a search tree. If every such subtree has a negative sum, return 0.
Trees appear in the tests in level order, with null for a missing child, like [3,9,20,null,null,15,7]. Each node is a TreeNode with .val, .left and .right; the class is already defined for you.
Example 1
Under 15 the value 7 sits on the wrong side, so neither that subtree nor the whole tree counts. The subtree at 5 is a search tree with sum 1 + 5 + 8 = 14.
Example 2
The whole tree is a search tree.
Example 3
The leaves are search trees, but their sums are below 0.
Constraints
1 <= number of nodes <= 40-1000 <= node.val <= 1000
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.
More Trees problems
- Same Up to Swapping ChildrenHard
- Tree From an OutlineHard
- Two Subtrees ApartHard
- Two Swapped ValuesHard
- Binary Tree Inorder TraversalBeginner
- Binary Tree Postorder TraversalBeginner
- Binary Tree Preorder TraversalBeginner
- Collect the LeavesBeginner