[数据结构与算法]LeetCode28_迭代、DFS_删点成林

题目描述

给出二叉树的根节点 root，树上每个节点都有一个不同的值。

如果节点值在 to_delete 中出现，我们就把该节点从树上删去，最后得到一个森林（一些不相交的树构成的集合）。

返回森林中的每棵树。你可以按任意顺序组织答案。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/delete-nodes-and-return-forest
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

我的解答

分析

• 开始想着很简单，直接迭代调用递归删除即可，试了试两个样例都通过了，直接提交发现远不止这些…第三个用例都没过…
• 千万不要眼高手低，有些细节想的还是不全面的，比如
  • 记录父节点改左、右孩子为null
  • 由于迭代顺序的问题导致树已经被截断，但是后面待删除的节点还未删除，而截断节点的子节点已经放到res中
  • …

过程中还报了一个并发修改异常，太坏了样例

思路改为

• 将待删除数组传递递归中迭代删除
• 删除完一个不是叶子节点，还要检查子节点，是否包含待删除
  res.add(root.left);
dfs(root.left,null,delete);
• 待删除的为节点也要考虑 res.remove(root);

/**
 * 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 {
    List<TreeNode> res = new LinkedList<>();
    TreeNode tree;
    public List<TreeNode> delNodes(TreeNode root, int[] to_delete) {
        this.tree = root;
        res.add(tree);
        dfs(tree,null,to_delete);
        return res;
        
    }
    public void dfs(TreeNode root,TreeNode father,int[] delete){
        if(root == null){
            return;
        }
        // 递归中迭代
        for(int i : delete){
            if(root.val == i){
                if(root.left != null){
                    res.add(root.left);
                    //  删除完一个不是叶子节点，还要检查子节点，是否包含待删除 
                    dfs(root.left,null,delete);
                }
                if(root.right != null){
                    res.add(root.right);
                    dfs(root.right,null,delete);
                }
                //  待删除的为节点也要考虑
                if(father == null){
                    res.remove(root);
                    return;
                }
                if(father.left == root){
                    father.left = null;
                }
                if(father.right == root){
                    father.right = null;
                }
                return;
            }

        }
        
        dfs(root.left,root,delete);
        dfs(root.right,root,delete);
    }
}