1. 題目

給定一棵二叉樹(shù)的根 root，請(qǐng)你考慮它所有 從根到葉的路徑：從根到任何葉的路徑。（所謂一個(gè)葉子節(jié)點(diǎn)，就是一個(gè)沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn)）

假如通過(guò)節(jié)點(diǎn) node 的每種可能的 “根-葉” 路徑上值的總和全都小于給定的 limit，則該節(jié)點(diǎn)被稱之為「不足節(jié)點(diǎn)」，需要被刪除。

請(qǐng)你刪除所有不足節(jié)點(diǎn)，并返回生成的二叉樹(shù)的根。

示例 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
輸出：[]

提示： 給定的樹(shù)有 1 到 5000 個(gè)節(jié)點(diǎn) -10^5 <= node.val <= 10^5 -10^9 <= limit <= 10^9

來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/insufficient-nodes-in-root-to-leaf-paths
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

2. 解題

class Solution {int sum = 0;//全局變量 public:TreeNode* sufficientSubset(TreeNode* root, int limit) {if(!root)return NULL;sum += root->val;//加入路徑sumif(!root->left && !root->right)//葉子節(jié)點(diǎn){if(sum < limit)//需要?jiǎng)h除節(jié)點(diǎn){sum -= root->val;return NULL;//一會(huì)父節(jié)點(diǎn)left或right指向nullptr}else//不刪{sum -= root->val;return root;//原封不動(dòng)，返回該節(jié)點(diǎn)}}else //非葉子節(jié)點(diǎn)，繼續(xù)往下+{root->left = sufficientSubset(root->left, limit);root->right = sufficientSubset(root->right, limit);//左右都處理完了sum -= root->val;//當(dāng)前節(jié)點(diǎn)要return了，減去它的值if(!root->left && !root->right)//左右至少有一個(gè)被刪了，且現(xiàn)在沒(méi)有子節(jié)點(diǎn)了return NULL;//它自己也需要被刪elsereturn root;}} };

總結(jié)

以上是生活随笔為你收集整理的LeetCode 1080. 根到叶路径上的不足节点（递归）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。