LeetCode1080-根到叶路径上的不足节点

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/letter-tile-possibilities/

中文链接：https://leetcode-cn.com/problems/letter-tile-possibilities/

题目详述

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

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

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

示例 1：

1
输入：root = [1,2,3,4,-99,-99,7,8,9,-99,-99,12,13,-99,14], limit = 1

1
输出：[1,2,3,4,null,null,7,8,9,null,14]

示例 2：

1
输入：root = [5,4,8,11,null,17,4,7,1,null,null,5,3], limit = 22

1
输出：[5,4,8,11,null,17,4,7,null,null,null,5]

示例 3：

1
2
输入：root = [5,-6,-6], limit = 0
输出：[]

提示：

  • 给定的树有 1 到 5000 个节点
  • -10^5 <= node.val <= 10^5
  • -10^9 <= limit <= 10^9

题目详解

  • 如果结点 root 为 null 直接返回 null。
  • 执行 limit -= root.val;。
  • 如果当前结点为叶结点，如果 limit > 0（表明从“根-叶” 路径上值的总和小于给定的 limit）返回 null，否则返回当前结点。
  • 对左右子树进行递归删除并进行赋值。
  • 注意如果结点的左孩子与右孩子均被删除，则此结点也要被删除。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class LeetCode_01080 {

    public TreeNode sufficientSubset(TreeNode root, int limit) {
        if (root == null) {
            return null;
        }
        limit -= root.val;
        if (root.left == null && root.right == null) {
            return limit > 0 ? null : root;
        }
        root.left = sufficientSubset(root.left, limit);
        root.right = sufficientSubset(root.right, limit);
        // 结点的左孩子与右孩子均被删除，则此结点也要被删除
        return root.left == null && root.right == null ? null : root;
    }
}