LeetCode 1080. 根到叶路径上的不足节点（递归）

Michael阿明

发布于 2020-07-13 17:08:16

7110

发布于 2020-07-13 17:08:16

文章被收录于专栏：Michael阿明学习之路

1. 题目

给定一棵二叉树的根 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 到 5000 个节点
-10^5 <= node.val <= 10^5
-10^9 <= limit <= 10^9

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/insufficient-nodes-in-root-to-leaf-paths 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

class Solution {
	int sum = 0;//全局变量
public:
    TreeNode* sufficientSubset(TreeNode* root, int limit) {
    	if(!root)
    		return NULL;
    	sum += root->val;//加入路径sum
    	if(!root->left && !root->right)//叶子节点
    	{
    		if(sum < limit)//需要删除节点
    		{
    			sum -= root->val;
    			return NULL;//一会父节点left或right指向nullptr
    		}
    		else//不删
    		{
    			sum -= root->val;
    			return root;//原封不动，返回该节点
    		}
    	}
    	else	//非叶子节点，继续往下+
    	{
    		root->left = sufficientSubset(root->left, limit);
    		root->right = sufficientSubset(root->right, limit);
            //左右都处理完了
    		sum -= root->val;//当前节点要return了，减去它的值
    		if(!root->left && !root->right)
    		//左右至少有一个被删了，且现在没有子节点了
    			return NULL;//它自己也需要被删
    		else
    			return root;
    	}
    }
};