Write a method named limitPathSum that removes nodes from a binary tree of integers to guarantee that the sum of the values on any path from the root to a node does not exceed some maximum value.
Your method accepts as its parameter a TreeNode that refers to the root of the tree and returns the tree's new root.
For example, suppose that a variable tree refers to the root of the following tree:
(29 (17 (-7 (11) (12)) (37 / (16))) (15 (4) (14 (-9) (19))))
Then the call of limitPathSum(tree, 50) will remove nodes so as to guarantee that no path from the root to a node has a sum that is greater than 50.
This will require removing the node with 12 because the sum of the values from the root to that node is greater than 50 (29 + 17 + -7 + 12 = 51).
Similarly, we have to remove the node with 37 because its sum is too high (29 + 17 + 37 = 83).
Whenever you remove a node, you remove anything under it as well, so removing 37 also removes 16.
We also remove the node with 14 and everything under it because its sum is high enough (29 + 15 + 14 = 58).
Thus we produce the following tree:
(29 (17 (-7 (11))) (15 (4)))
The method would remove all nodes if the data stored at the root is greater than the given maximum.
This would cause the method to return a new null root.
Assume that you are interacting with TreeNodes as defined below:
public class TreeNode {
public int data;
public TreeNode left;
public TreeNode right;
public TreeNode() { ... }
public TreeNode(int data) { ... }
public TreeNode(int data, TreeNode left, TreeNode right) { ... }
}
