LeetCode刷题系列 -- 1080. 根到叶路径上的不足节点

给定一棵二叉树的根 root请你考虑它所有 从根到叶的路径从根到任何叶的路径。所谓一个叶子节点就是一个没有子节点的节点

假如通过节点 node 的每种可能的 “根-叶” 路径上值的总和全都小于给定的 limit则该节点被称之为「不足节点」需要被删除。

请你删除所有不足节点并返回生成的二叉树的根。

示例 1

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

输出[1,2,3,4,null,null,7,8,9,null,14]

示例 2

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

输出[5,4,8,11,null,17,4,7,null,null,null,5]

示例 3

输入root = [5,-6,-6], limit = 0

输出[]

提示

1. 给定的树有 1 到 5000 个节点

2. -10^5 <= node.val <= 10^5

3. -10^9 <= limit <= 10^9

https://leetcode.cn/problems/insufficient-nodes-in-root-to-leaf-paths/description/

思路

当节点为叶子节点时节点是否删除取决于 limit 减去着一路所经过的节点不包含当前叶子节点的和 A 若是当前叶子节点的值小于 A则当前叶子节点需要被删除反之不用
当节点为非叶子节点时节点是否删除取决于 它的孩子结点只要其孩子结点有一个被保留父亲结点就不能被删换句话说父亲结点被删除当且仅当它的两个孩子结点均被删除即在原二叉树中该节点属于 不足节点

c++

/**
 * 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 == nullptr && root->right == nullptr) {

            // 当递归到叶子节点后若是叶子节点的值小于 limit说明从根节点到该叶子叶子节点中存在不足节点该叶子节点本身也属于不足节点需要删除
            if(root->val < limit) {
                return nullptr;
            } else {
                return root;
            }
        }

        // 当一个结点不是叶子结点的时候它是否被删除要看它的孩子结点只要其孩子结点有一个被保留父亲结点就不能被删换句话说父亲结点被删除当且仅当它的两个孩子结点均被删除即在原二叉树中该节点属于 不足节点

        root->left = sufficientSubset(root->left, limit - root->val);
        root->right = sufficientSubset(root->right, limit - root->val);

    

        // 当 root 节点 的孩子节点都被删除后说明根节点无法通过 root 节点到达叶子节点root 节点属于 不足节点故而删除
        if(root->left == nullptr && root->right == nullptr) {
            return nullptr;
        }

        // 若是 root 还有孩子节点则不用删除
        return root;
    }

};