题目描述

给你二叉树的根节点 root 和一个整数 limit ，请你同时删除树中所有** 不足节点 **，并返回最终二叉树的根节点。

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

叶子节点，就是没有子节点的节点。

提示：

• 树中节点数目在范围 [1, 5000] 内
• -105 <= Node.val <= 105
• -109 <= limit <= 109

测试用例

用例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 = [1,2,-3,-5,null,4,null], limit = -1
• 输出：[1,null,-3,4]

代码实现

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} limit
 * @return {TreeNode}
 */
var sufficientSubset = function(root, limit) {
    // 先序遍历，同时记录和
  	// 注意：空节点返回false，因为此时false的效果就跟返回Null是一样的
    // 大于等于limit 则不是不足结点 返回true 不删除
    // 小于limit 则是不足结点 返回false 要删除
    // 最后返回的是 —— 左右子树有true就返回true，同时为false返回false

    let traversal = (node, sum, limit) => {
        // 处理空结点
        if(node == null){
            return false;
        }
        // 处理叶子结点
        if(node.left == null && node.right == null){
            return sum + node.val >= limit;
        }
        
        const leftSub = traversal(node.left, sum + node.val, limit);
        const rightSub = traversal(node.right, sum + node.val, limit);

        // 是不足结点就删除
        if(!leftSub){
            node.left = null;
        }
        if(!rightSub){
            node.right = null;
        }
        console.log("leftSub:", leftSub);
        console.log("rightSub: ", rightSub);
        console.log("test: ", leftSub || rightSub);
        return leftSub || rightSub;
    }

    const res = traversal(root, 0, limit);
    // 判断最后是否为空
    return res ? root : null;
};