[LeetCode] 1080. 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.

Example 1:

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

Output: [1,2,3,4,null,null,7,8,9,null,14]

Example 2:

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

Output: [5,4,8,11,null,17,4,7,null,null,null,5]

Example 3:

Input: root = [1,2,-3,-5,null,4,null], limit = -1

Output: [1,null,-3,4]

Note:

The given tree will have between 1 and 5000 nodes.
-10^5 <= node.val <= 10^5
-10^9 <= limit <= 10^9

根到叶路径上的不足节点。

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

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

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

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

这道题的题意是对于所有从根节点 root 到叶子节点的路径，如果有发觉某条路径上的路径和最终严格小于 limit，就把这条路径上的 node 删除，但是不能删除过多 node 导致其他合法的路径也消失。

这里我提供一个后序遍历的做法。为什么是后序遍历是因为节点只有可能从叶子节点开始删除，不可能是从根节点开始删除。这里我们需要一个helper函数，注意以下几点

helper函数的base case是遇到叶子节点，当某个节点没有左右孩子的时候，就可以结算了，结算的方式是之前的节点值的和 sum + 当前节点node.val 是否小于limit，如果小于就返回true - 意思是需要把当前这个节点删除

对于左右子树，我们也递归去这样判断

时间O(n)

空间O(n)

Java实现

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     int val;
 5  *     TreeNode left;
 6  *     TreeNode right;
 7  *     TreeNode() {}
 8  *     TreeNode(int val) { this.val = val; }
 9  *     TreeNode(int val, TreeNode left, TreeNode right) {
10  *         this.val = val;
11  *         this.left = left;
12  *         this.right = right;
13  *     }
14  * }
15  */
16 class Solution {
17     public TreeNode sufficientSubset(TreeNode root, int limit) {
18         boolean rootDeleted = helper(root, 0, limit);
19         if (rootDeleted) {
20             return null;
21         }
22         return root;
23     }
24 
25     private boolean helper(TreeNode node, int sum, int limit) {
26         // base case, when we at the left node
27         if (node.left == null && node.right == null) {
28             return sum + node.val < limit;
29         }
30         boolean leftDelete = true;
31         boolean rightDelete = true;
32         if (node.left != null) {
33             leftDelete = helper(node.left, sum + node.val, limit);
34         }
35         if (node.right != null) {
36             rightDelete = helper(node.right, sum + node.val, limit);
37         }
38         if (leftDelete) {
39             node.left = null;
40         }
41         if (rightDelete) {
42             node.right = null;
43         }
44         return leftDelete && rightDelete;
45     }
46 }

LeetCode 题目总结