Insufficient Nodes in Root to Leaf Paths

https://leetcode.com/contest/weekly-contest-140/problems/insufficient-nodes-in-root-to-leaf-paths/

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.

Thoughts

二叉树，对任意点，如果每条经过该点的root到原树leaf的路径的和都小于limit, 则删除改点。

1. 如果当前点原本是leaf, 判断现在的sum是否小于limit. 小于则代表该leaf应该被删掉，返回NULL.

2. 二叉树想分治。假设左右子树已经清理完毕，当左/右返回NULL代表左/右整个都要删掉。从上往下把limit-=node->val. 当该节点变为新leaf时，返回NULL.

class Solution {
public:
    TreeNode* sufficientSubset(TreeNode* root, int limit) {
        if (root == NULL) return root;
        // If it is a leaf, check whether val satisfies the limit. Return null => del this node.
        if (root->left == root->right) return root->val < limit ? NULL : root;
        // Divide and conquer.
        root->left = sufficientSubset(root->left, limit - root->val);
        root->right = sufficientSubset(root->right, limit - root->val);
        // If it becomes a new leaf, return null.
        return root->left == root->right ? NULL : root;
    }
};

Analysis

每个节点访问一次，时间复杂度O(N). 空间复杂度和递归深度有关