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
and5000
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 }