LEETCODE 1273. Delete Tree Nodes 解题思路分析

题目大意:

删除树节点

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

  • 节点的总数为 nodes 个
  • 第 i 个节点的值为 value[i]
  • 第 i 个节点的父节点是 parent[i]

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

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

示例1:

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

提示:

  • 1 <= nodes <= 10^4
  • -10^5 <= value[i] <= 10^5
  • parent.length == nodes
  • parent[0] == -1 表示节点 0 是树的根。

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

解题思路分析:

本题需要先对节点进行整理,题目给出了每个节点的父节点,这不利于做题,因此我们需要统计出每个节点的子节点有哪些。

统计出子节点信息后,我们使用递归方式从根节点开始查看每个节点下(包含当前节点)所有节点的和,如果当前节点(当前子树)下所有节点和为0,那么,可将当前节点下的子节点清空(相当于删除节点操作),同时当前节点值变为0。递归结束时,总和为0的子树子节点都会被删除,注意子树的根节点没被删除,只是值变为0而已。

节点删除操作结束之后,我们就可以统计剩下的节点数量,还是使用递归,从根节点开始递归统计每个节点下子节点的数量,如果当前节点为叶子节点,当值为0时,返回0,非0时,返回个数1。

实现代码:

List<Integer>[] children; // 每个节点的子节点
public int deleteTreeNodes(int nodes, int[] parent, int[] value) {
    children = new List[nodes];
    for(int i=0;i<nodes;i++){
        children[i]=new ArrayList<>();
    }
    // 统计每个节点的子节点
    for(int i=0;i<nodes;i++){
        int root=parent[i];
        if(root==-1) continue;
        children[root].add(i);
    }
    // 删除和为0的子树
    helper(value, parent, 0);
    // 统计删除后剩余节点数量,返回。
    return count(0, value);
}
int helper(int[] value, int[] parent, int index){
    int sum=value[index];
    for(int child : children[index]){
        sum+=helper(value, parent, child);
    }
    if(sum==0){
        children[index].clear();
        value[index]=0;
    }
    return sum;
}
int count(int index, int[] value){
    if(children[index].size()==0){
        return value[index]==0 ? 0:1;
    }
    int count=1;
    for(int child : children[index]){
        count+=count(child, value);
    }
    return count;
}

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

Runtime: 13 ms, faster than 60.57% of Java online submissions for Delete Tree Nodes.

Memory Usage: 40.5 MB, less than 100.00% of Java online submissions for Delete Tree Nodes.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: https://leetcode.jp/leetcode-1273-delete-tree-nodes-解题思路分析/
此条目发表在leetcode分类目录,贴了, , 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。