X

LEETCODE 1080. Insufficient Nodes in Root to Leaf Paths 解题思路分析

题目大意:

根到叶路径上的不足节点

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

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

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

示例 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
输出:[]

提示:

  1. 给定的树有 15000 个节点
  2. -10^5 <= node.val <= 10^5
  3. -10^9 <= limit <= 10^9

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1080

解题思路分析:

这是一道二叉树的题目,LEETCODE中此类题目不在少数。需要遍历所有路径时,应下意识想到递归或者说是dfs搜索。本题也应该使用到递归方式来解题。

题目要求求出所有根节点到所有叶子节点的路径,每条路径上的节点和不能小于limit。如果通过某一个节点的所有路径的和都小于limit,那么这个节点应该被删除。我们需要遍历每一条路径,查看root到叶子间的和是否满足条件。进而对于任意一个节点,如果它左右两条分支下的所有路径均不符合条件,就应该删除当前节点。

我们利用递归函数先遍历到每个叶子节点,递归函数的参数中需要传入一个当前的节点和,到叶子节点时,如果这个和小于limit,说明该路径是非法路径,由于叶子节点只存在当前这唯一的路径,因此该叶子节点应当被删除,返回null,反之则应该被保留,将当前节点返回到递归上层函数。

对于非叶子节点,我们可以利用递归函数分别得到左右两个子节点,如果两个节点均为空,说明左右两条路径均为非法路径,当前节点应当被删除,返回null给上层递归函数,反之则说明存在合法路径,可将当前节点返回给上层递归函数。直到回溯到root,递归结束,root即是最终答案。

看下完整代码。

public TreeNode sufficientSubset(TreeNode root, int limit) {
    return help(root, limit, 0);
}

TreeNode help(TreeNode root, int limit, int sum){
    if(root == null){ // 当前节点为空,返回空
        return null;
    }
    if(root.right==null && root.left==null){ // 叶子节点
        return sum + root.val < limit ? null : root; // 判断该路径和是否合法,非法时返回空
    }
    // 非叶子节点
    TreeNode left = help(root.left, limit, sum + root.val); // 递归得到左节点
    TreeNode right = help(root.right, limit, sum + root.val); // 递归得到右节点
    root.left=left;
    root.right=right;
    if(left==right){ // 左右节点均为空,说明无合法路径,返回空
        return null;
    }else{
        return root; // 存在合法路径,返回当前节点
    }
}

本解法用时1ms。

Runtime: 1 ms, faster than 100.00% of Java online submissions for Insufficient Nodes in Root to Leaf Paths.

Memory Usage: 38.5 MB, less than 100.00% of Java online submissions for Insufficient Nodes in Root to Leaf Paths.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: https://leetcode.jp/leetcode-1080-insufficient-nodes-in-root-to-leaf-paths-解题思路分析/
Categories: leetcode
kwantong: