Leetcode 1273:删除树节点(超详细的解法!!!)
in leetcode with 0 comment

Leetcode 1273:删除树节点(超详细的解法!!!)

in leetcode with 0 comment

给你一棵以节点 0 为根节点的树,定义如下:

请你删除节点值之和为 0 的每一棵子树。

在完成所有删除之后,返回树中剩余节点的数目。

示例:

输入:nodes = 7, parent = [-1,0,0,1,2,2,2], value = [1,-2,4,0,-2,-1,-1]
输出:2

提示:

解题思路

树型问题首先思考dfs解法。首先我们需要通过parent构建树,然后递归。递归中需要处理当前节点为根的子树和sumAll和节点个数cnt。当sumAll0的时候,返回节点个数为0即可。

class Solution:
    def deleteTreeNodes(self, nodes: int, parent: List[int], value: List[int]) -> int:
        tree = collections.defaultdict(list)
        for i, v in enumerate(parent):
            tree[v].append(i)
            
        def dfs(cur):
            sumAll, cnt = value[cur], 1
            for ne in tree[cur]:
                t, c = dfs(ne)
                sumAll += t
                cnt += c 
            return sumAll, cnt if sumAll else 0
        
        return dfs(0)[1]

这个问题还有一个更加好的解法。我们可以将value的值从后(叶子节点)向前(根节点)加。然后再从前向后统计0的个数,如果此时遍历到的元素的父节点值是0,那么意味着当前元素需要删除(将其标记成0),可以通过如下操作实现:

if parent[i] and isZero[parent[i]] or value[i]:
    isZero[i] = 0

最后代码如下

class Solution:
    def deleteTreeNodes(self, n: int, parent: List[int], value: List[int]) -> int:
        for i in range(n-1, 0, -1):
            value[parent[i]] += value[i]
        
        zeros, isZero = 0, [0] * n
        for i in range(n):
            if parent[i] > 0 and isZero[parent[i]] or value[i] == 0:
                isZero[i] = 1
                zeros += 1
        return n - zeros

这个代码的效率很高,但是需要一些条件满足:这些节点必须是从上到下有序的(按照层序遍历得到parent数组)。

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题,希望大家指出!!!

「如果我的文章对你有很大帮助,那么不妨~!」

coordinate

谢谢老板O(∩_∩)O~

使用微信扫描二维码完成支付

Responses