Solution to Leetcode problem 1080: Insufficient Nodes in Root to Leaf Paths

This is the exact question from Leetcode:

Given the root of a binary tree, consider all root to leaf paths: paths from the root to any leaf.  (A leaf is a node with no children.)
A node is insufficient if every such root to leaf path intersecting this node has sum strictly less than limit.
Delete all insufficient nodes simultaneously, and return the root of the resulting binary tree.

I like this question because:

1. It is about binary tree
2. It only requires a simple traversal to solve the problem, once you think about it

For each node, we need to generate the max sum for all leaf path intersecting with that node, this can be done recursively. If this max is less than the limit, the node should be removed, if the max is higher or equal to the limit, the node should not be removed.

As we go down the tree for recursion, we need to keep track of the current sum from the root to the current node being visited (that I called current).

What’s more, since we need to visit all the children of the node to find which one is max, and what to do with the node, it seems that a post order traversal is the best way to go!

The way I am doing it. I do a recursive call on the left child and on the right child. It will give me the max for the left child. If the max for the left…