4. Tree

一步到位：

• path sum II

• Delete Nodes and return forest

Delete Nodes and Return Forest

• 好题！

• 这题是个典型的Tree problem-> Sub problem-> recursion

• Tree Recursion的实现时有两个关键点

  • passing info downwards -- by arguments

  • passing info upwards -- by return value

• pass parent node as argument

• 然后判断toDelete.contains(cur.val) 来处理不同情况

• D& C也是post order traversal

class Solution {
    /*
    when to add curNode to list?-> if parentNode is being deleted and curNode is not delete
    */
    public List<TreeNode> delNodes(TreeNode root, int[] to_delete) {
        List<TreeNode> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        Set<Integer> toDelete = new HashSet<>();
        for (int delete : to_delete) {
            toDelete.add(delete);
        }
        helper(res, toDelete, root, null);
        return res;
    }
    //return new tree of cur after processing
    //check whether cur needs to be deleted
    //D& C
    private TreeNode helper(List<TreeNode> res, Set<Integer> toDelete, TreeNode cur, TreeNode parent) {
        if (cur == null) return null;
        cur.left = helper(res, toDelete, cur.left, cur);
        cur.right = helper(res, toDelete, cur.right, cur);
        //when to add to res
        if (toDelete.contains(cur.val)) {
            return null;
        } else {
            //2 conditions:cur== rot | parent is to delete
            if (parent == null || toDelete.contains(parent.val)) {
                res.add(cur);
            }
        }
        return cur;
    }
}