1080. Insufficient Nodes in Root to Leaf Paths -------M !!!!!!~~~~~!!!!!!!!!!

 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.

 

Example 1:

Input: root = [1,2,3,4,-99,-99,7,8,9,-99,-99,12,13,-99,14], limit = 1

Output: [1,2,3,4,null,null,7,8,9,null,14]

Example 2:

Input: root = [5,4,8,11,null,17,4,7,1,null,null,5,3], limit = 22

Output: [5,4,8,11,null,17,4,7,null,null,null,5]

 

Example 3:

Input: root = [1,2,-3,-5,null,4,null], limit = -1

Output: [1,null,-3,4]

 

Note:

1. The given tree will have between 1 and 5000 nodes.
2. -10^5 <= node.val <= 10^5
3. -10^9 <= limit <= 10^9

A:

经典的DFS啊，可是为啥你花了2个小时，还是每寻思明白呢？太弱了，  Tiger

下次自己再想想 ~~~~~

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* sufficientSubset(TreeNode* root, int limit) {
        if( ! root){ // nullptr
            return nullptr;
        }
        if(!root->left && !root->right){// if leaf
            if(root->val >= limit){
                return root;
            }else{
                return nullptr;
            }
        }
        root->left = sufficientSubset(root->left, limit - root->val);
        root->right = sufficientSubset(root->right, limit - root->val);
        if(!root->left && !root->right){ // if all child have been deleted
            return nullptr;
        }else{
            return root;
        }
    }
};