X

LEETCODE 1325. Delete Leaves With a Given Value 解题思路分析

题目大意:

删除给定值的叶子节点

给你一棵以 root 为根的二叉树和一个整数 target ,请你删除所有值为 target 的 叶子节点 。

注意,一旦删除值为 target 的叶子节点,它的父节点就可能变成叶子节点;如果新叶子节点的值恰好也是 target ,那么这个节点也应该被删除。

也就是说,你需要重复此过程直到不能继续删除。

示例 1:

输入:root = [1,2,3,2,null,2,4], target = 2
输出:[1,null,3,null,4]
解释:
 上面左边的图中,绿色节点为叶子节点,且它们的值与 target 相同(同为 2 ),它们会被删除,得到中间的图。
 有一个新的节点变成了叶子节点且它的值与 target 相同,所以将再次进行删除,从而得到最右边的图。

示例 2:

输入:root = [1,3,3,3,2], target = 3
输出:[1,3,null,null,2]

示例 3:

输入:root = [1,2,null,2,null,2], target = 2
输出:[1]
解释:每一步都删除一个绿色的叶子节点(值为 2)。

示例 4:

输入:root = [1,1,1], target = 1
输出:[]

示例 5:

输入:root = [1,2,3], target = 1
输出:[1,2,3]

提示:

  • 1 <= target <= 1000
  • 每一棵树最多有 3000 个节点。
  • 每一个节点值的范围是 [1, 1000]

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

解题思路分析:

之前文章多次强调过,关于树的题目多数要考虑使用dfs或者bfs来解题,本题需要删除某些满足条件的叶子节点,即我们需要遍历所有路径找到叶子节点,因此dfs应是最优选择。

解题时,先判断当前节点,如果为空,直接返回空。之后一路递归左右子节点到其叶子节点,如果当前叶子节点的值等于 target ,说明当前叶子节点需要被删除,返回空,否则返回该叶子节点,并回到上一层递归。在上一层递归中判断当前节点是否变成了叶子节点,如果是,则需判断当前节点的值是否等于target,如果是也应被删除掉,返回空,否则返回当前节点。

实现代码:

public TreeNode removeLeafNodes(TreeNode root, int target) {
    // 如果当前节点为空,返回空
    if(root==null) return null;
    // 当前节点左节点等于递归dfs左节点的值
    root.right=removeLeafNodes(root.right, target);
    // 当前节点右节点等于递归dfs右节点的值
    root.left=removeLeafNodes(root.left, target);
    // 如果当前节点为叶子节点(左右子节点均为空),并且当前节点值为target
    if(root.right==null&&root.left==null&&root.val==target){
        // 删除当前节点
        root=null;
    }
    // 返回当前节点
    return root;
}

本题解法执行时间为0ms。

Runtime: 0 ms, faster than 100.00% of Java online submissions for Delete Leaves With a Given Value.

Memory Usage: 45 MB, less than 100.00% of Java online submissions for Delete Leaves With a Given Value.

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