LeetCode 1110. 删点成林

Categories:

题目描述
思路分析
1. 解法一：后序 DFS（推荐）
相似题目

题目描述

✅ 1110. 删点成林

思路分析

解法一：后序 DFS（推荐）

核心思路：

用哈希集合记录需要删除的节点值。

后序遍历，先处理左右子树，再决定当前节点是否删除。

若删除当前节点，则其非空子节点加入结果森林。

复杂度分析：

时间复杂度：O(n)，其中 n 表示节点数。

空间复杂度：O(n)，递归栈和集合开销。

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

class Solution {
    public List<TreeNode> delNodes(TreeNode root, int[] to_delete) {
        Set<Integer> del = new HashSet<>();
        for (int v : to_delete) {
            del.add(v);
        }

        List<TreeNode> forest = new ArrayList<>();
        root = dfs(root, del, forest);
        if (root != null) {
            forest.add(root);
        }

        return forest;
    }

    private TreeNode dfs(TreeNode node, Set<Integer> del, List<TreeNode> forest) {
        if (node == null) {
            return null;
        }

        node.left = dfs(node.left, del, forest);
        node.right = dfs(node.right, del, forest);

        if (del.contains(node.val)) {
            if (node.left != null) {
                forest.add(node.left);
            }
            if (node.right != null) {
                forest.add(node.right);
            }
            return null;
        }

        return node;
    }
}

func delNodes(root *TreeNode, toDelete []int) []*TreeNode {
	del := make(map[int]bool)
	for _, v := range toDelete {
		del[v] = true
	}

	forest := make([]*TreeNode, 0)
	root = dfsDel(root, del, &forest)
	if root != nil {
		forest = append(forest, root)
	}

	return forest
}

func dfsDel(node *TreeNode, del map[int]bool, forest *[]*TreeNode) *TreeNode {
	if node == nil {
		return nil
	}

	node.Left = dfsDel(node.Left, del, forest)
	node.Right = dfsDel(node.Right, del, forest)

	if del[node.Val] {
		if node.Left != nil {
			*forest = append(*forest, node.Left)
		}
		if node.Right != nil {
			*forest = append(*forest, node.Right)
		}
		return nil
	}

	return node
}

相似题目

题目	难度	考察点
1110. 删点成林	中等	树、DFS
814. 二叉树剪枝	中等	树、DFS
669. 修剪二叉搜索树	中等	BST、DFS
450. 删除二叉搜索树中的节点	中等	BST
1325. 删除给定值的叶子节点	中等	树、DFS

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/81195471