golang 解法, 执行用时: 12 ms, 内存消耗: 6.4 MB, 提交时间: 2023-05-30 09:39:45

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func delNodes(root *TreeNode, toDelete []int) (ans []*TreeNode) {
    set := make(map[int]struct{}, len(toDelete))
    for _, x := range toDelete {
        set[x] = struct{}{}
    }
    var dfs func(*TreeNode) *TreeNode
    dfs = func(node *TreeNode) *TreeNode {
        if node == nil {
            return nil
        }
        node.Left = dfs(node.Left)
        node.Right = dfs(node.Right)
        if _, ok := set[node.Val]; !ok {
            return node
        }
        if node.Left != nil {
            ans = append(ans, node.Left)
        }
        if node.Right != nil {
            ans = append(ans, node.Right)
        }
        return nil
    }
    if dfs(root) != nil {
        ans = append(ans, root)
    }
    return
}

java 解法, 执行用时: 1 ms, 内存消耗: 42.8 MB, 提交时间: 2023-05-30 09:39:21

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<TreeNode> delNodes(TreeNode root, int[] toDelete) {
        var ans = new ArrayList<TreeNode>();
        var s = new HashSet<Integer>();
        for (int x : toDelete) s.add(x);
        if (dfs(ans, s, root) != null) ans.add(root);
        return ans;
    }

    private TreeNode dfs(List<TreeNode> ans, Set<Integer> s, TreeNode node) {
        if (node == null) return null;
        node.left = dfs(ans, s, node.left);
        node.right = dfs(ans, s, node.right);
        if (!s.contains(node.val)) return node;
        if (node.left != null) ans.add(node.left);
        if (node.right != null) ans.add(node.right);
        return null;
    }
}

python3 解法, 执行用时: 72 ms, 内存消耗: 16.6 MB, 提交时间: 2023-05-30 09:38:58

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:
        ans = []
        s = set(to_delete)
        def dfs(node: Optional[TreeNode]) -> Optional[TreeNode]:
            if node is None: return None
            node.left = dfs(node.left)
            node.right = dfs(node.right)
            if node.val not in s: return node
            if node.left: ans.append(node.left)
            if node.right: ans.append(node.right)
            return None
        if dfs(root): ans.append(root)
        return ans

golang 解法, 执行用时: 8 ms, 内存消耗: 6.2 MB, 提交时间: 2022-11-28 14:51:54

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func delNodes(root *TreeNode, to_delete []int) []*TreeNode {
    ret :=  []*TreeNode{}
    st := make(map[int]int)
    for _,v := range to_delete{
        st[v] = v
    }
    var postOrder func(parent *TreeNode,node *TreeNode)
    postOrder = func (parent *TreeNode,node *TreeNode) {
        if node == nil{
            return
        }
    postOrder(node,node.Left)
    postOrder(node,node.Right)

    if _,ok := st[node.Val];ok{
            if parent != nil {
                if parent.Left == node {
                    parent.Left = nil
                }
                if parent.Right == node {
                    parent.Right = nil
                }
            }
            if node.Left != nil {
                ret = append(ret,node.Left)
            }
            if node.Right != nil {
                ret = append(ret,node.Right)
            }
        }
    }
    postOrder(nil,root)
    if _,ok := st[root.Val];!ok {
            ret = append(ret,root)
    }
    return ret
}

java 解法, 执行用时: 3 ms, 内存消耗: 42.2 MB, 提交时间: 2022-11-28 14:50:16

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    Set<Integer> toDelete;
    public List<TreeNode> delNodes(TreeNode root, int[] to_delete) {
        toDelete = Arrays.stream(to_delete).boxed().collect(Collectors.toSet());
        List<TreeNode> ans = new ArrayList<>();
        helper(root, ans, false);
        return ans;
    }

    boolean helper(TreeNode root, List<TreeNode> ans, boolean parentExists) {
        boolean del = false;
        if (root == null) {
            return del;
        }
        del = toDelete.contains(root.val);
        if (helper(root.left, ans, !del)) {
            root.left = null;
        }
        if (helper(root.right, ans, !del)) {
            root.right = null;
        }
        if (!del && !parentExists) {
            ans.add(root);
        }
        return del;
    }
}

python3 解法, 执行用时: 72 ms, 内存消耗: 15.5 MB, 提交时间: 2022-11-28 14:49:41

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def delNodes(self, root: TreeNode, to_delete: List[int]) -> List[TreeNode]:
        def dfs(root, hasParent):
            if not root:
                return False
            
            toDelete = root.val in to_delete
            # a new root = (keep root) and (has no parent)
            if not toDelete and not hasParent:
                res.append(root)

            # delete left = (delete left) and (keep root)
            if dfs(root.left, not toDelete):
                root.left = None
            
            # delete right = (delete right) and (keep root)
            if dfs(root.right, not toDelete):
                root.right = None
            return toDelete
        
        to_delete = set(to_delete)
        res = []
        dfs(root, False)
        return res