---
tags: leetcode
---

# [1110. Delete Nodes And Return Forest](https://leetcode.com/problems/delete-nodes-and-return-forest/)
---
# My Solution
## The Key Idea for Solving This Coding Question
## C++ Code

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

class Solution {
public:
    vector<TreeNode *> delNodes(TreeNode *root, vector<int> &to_delete) {
        unordered_set<int> deleteSet(to_delete.begin(), to_delete.end());
        vector<TreeNode *> forest;

        TreeNode *x = dfs(root, deleteSet, forest);
        if (x != nullptr) {
            forest.push_back(x);
        }

        return forest;
    }

private:
    TreeNode *dfs(TreeNode *root, unordered_set<int> &deleteSet, vector<TreeNode *> &forest) {
        if (root == nullptr) {
            return nullptr;
        }

        root->left = dfs(root->left, deleteSet, forest);
        root->right = dfs(root->right, deleteSet, forest);
        if (deleteSet.count(root->val) != 0) {
            if (root->left != nullptr) {
                forest.push_back(root->left);
            }
            if (root->right != nullptr) {
                forest.push_back(root->right);
            }
            delete root;
            return nullptr;
        }
        return root;
    }
};

## Time Complexity
## Space Complexity
# Miscellaneous
<!--
# Test Cases

[1,2,3,4,5,6,7]
[3,5]

[1,2,4,null,3]
[3]

[1,2,3,null,null,null,4]
[2,1]

[1,11,2,50,13,3,26,60,985,22,21,4,8,51,724,73,513,null,null,118,27,24,210,38,5,12,15,603,291,null,null,102,null,null,null,196,null,29,59,85,127,232,243,95,49,6,16,25,44,19,53,633,841,312,319,335,120,675,null,35,92,636,71,166,386,209,171,null,480,499,null,143,98,82,74,7,54,17,101,39,33,99,546,52,20,57,72,null,null,null,null,431,null,null,706,433,null,506,147,734,null,75,69,271,430,null,null,158,108,176,534,null,null,712,224,185,482,646,730,null,null,377,170,141,487,123,107,229,109,14,9,67,76,23,43,958,149,47,58,151,207,163,222,null,null,190,317,28,981,191,null,104,311,610,451,null,825,null,765,605,null,236,231,null,null,162,84,878,641,338,398,687,570,null,null,null,387,188,null,null,null,994,null,584,null,null,null,533,500,null,760,775,null,457,683,296,943,670,208,null,662,260,167,164,258,256,237,308,257,30,32,10,18,729,78,106,374,42,36,48,134,null,null,160,608,61,145,66,63,294,740,369,214,null,228,517,380,553,341,619,837,79,97,null,null,241,422,194,113,936,524,991,null,null,477,null,null,null,null,869,null,515,298,280,275,780,923,240,484,null,974,null,null,396,414,null,null,null,774,null,null,458,null,239,824,null,null,null,null,934,772,590,778,null,null,null,null,null,null,null,null,813,416,null,null,697,null,449,null,768,null,626,429,null,984,419,618,null,502,null,367,null,385,522,436,284,null,195,34,62,130,40,31,41,37,null,null,80,89,979,622,null,null,265,45,56,111,null,138,571,246,242,225,null,null,68,96,632,217,119,129,65,180,593,535,null,null,486,460,249,287,null,473,null,null,null,403,893,null,null,491,null,null,null,null,253,152,498,202,null,536,null,null,596,466,358,137,null,null,548,568,null,null,908,600,900,null,null,635,657,null,null,812,null,405,null,956,null,null,969,456,690,708,null,null,null,796,933,null,null,null,539,543,292,null,null,null,null,null,null,null,null,882,null,null,null,null,null,844,758,null,835,null,null,null,null,null,868,606,null,null,794,null,null,null,null,null,519,null,562,null,904,856,null,461,653,null,547,282,174,153,86,null,252,542,262,140,81,46,753,90,55,440,122,200,93,235,null,null,829,652,290,null,303,77,64,125,112,139,null,250,null,null,251,705,447,null,454,859,156,null,201,339,null,null,300,219,175,168,155,238,70,875,465,267,null,null,null,null,null,623,null,905,474,null,null,309,null,595,901,null,null,null,580,551,946,442,307,270,575,null,911,356,655,null,640,null,559,null,null,null,391,612,625,null,631,null,null,930,642,677,null,null,656,null,null,null,null,null,607,null,null,null,null,null,null,686,null,null,null,null,null,null,null,null,null,null,null,594,331,null,null,null,null,null,null,790,null,null,null,null,789,883,null,null,null,null,null,null,null,null,null,null,null,577,null,null,null,583,407,463,421,726,199,399,94,121,261,540,737,695,373,279,218,144,88,446,165,100,null,null,340,172,444,390,null,483,161,223,227,233,105,114,459,342,null,null,725,null,544,370,791,null,110,159,142,213,126,660,274,372,184,423,318,792,277,362,null,null,472,598,null,836,null,922,269,189,null,null,455,348,378,349,263,255,389,null,363,183,301,203,247,null,87,83,null,null,null,null,null,561,null,null,null,963,851,507,537,null,null,null,null,null,null,629,565,null,null,null,null,null,323,884,495,381,643,751,null,null,555,null,null,748,null,null,676,703,853,412,null,null,null,649,null,null,null,null,null,null,null,null,848,667,741,867,null,null,null,800,644,383,null,965,null,857,null,null,null,null,null,null,503,721,950,822,null,673,null,854,704,null,410,692,150,266,197,718,313,null,null,null,null,null,null,null,null,858,327,988,288,425,146,192,115,124,492,468,846,null,103,211,null,null,null,null,833,977,null,604,664,806,187,null,413,574,264,281,278,731,173,133,117,182,null,null,448,null,null,null,795,null,639,375,949,null,295,268,null,259,346,null,521,382,181,452,null,815,493,null,null,896,784,198,null,null,953,320,null,null,478,null,550,null,952,null,null,null,null,null,null,null,681,299,193,326,820,null,371,879,586,402,null,579,304,null,null,694,408,843,400,998,215,null,552,638,735,206,332,null,91,154,178,131,773,null,null,null,null,null,927,862,871,null,811,null,912,566,894,892,null,null,752,847,945,785,860,null,null,null,null,767,null,null,null,null,null,null,null,966,665,674,null,887,null,null,null,777,787,null,null,null,null,null,732,null,null,null,null,null,null,null,995,592,null,null,null,976,834,null,679,null,null,null,null,null,707,485,769,null,186,177,324,325,541,null,920,null,315,938,null,null,350,379,null,null,388,null,426,928,157,501,671,651,116,355,169,443,613,null,null,null,null,null,132,null,361,283,null,null,null,null,null,685,720,null,null,null,798,345,743,475,null,null,297,302,289,558,401,null,null,1000,null,null,216,230,347,453,null,328,616,null,null,null,null,776,764,null,null,null,null,null,null,null,529,364,918,357,null,null,750,624,716,850,757,null,null,null,578,497,null,null,895,913,null,365,null,967,494,972,null,745,839,null,null,null,null,null,310,469,285,245,null,479,null,null,523,null,null,null,null,628,755,null,null,null,351,439,978,null,415,null,null,null,525,490,null,null,441,450,null,736,null,null,null,982,305,212,333,null,739,null,276,352,226,null,135,null,null,null,null,null,null,null,null,null,null,null,null,null,990,null,null,null,null,null,null,null,null,864,null,null,null,null,null,null,null,null,null,null,null,992,null,null,932,null,null,null,null,null,null,907,null,null,627,650,null,null,null,null,null,null,null,null,881,null,null,null,220,514,221,204,null,null,937,556,null,797,null,null,null,634,null,null,353,715,null,861,null,471,null,null,null,null,272,205,null,993,null,733,null,964,179,128,null,508,254,334,null,null,null,null,709,286,409,417,null,573,null,null,null,null,null,null,557,710,null,null,511,null,983,397,435,337,438,668,654,null,445,null,null,null,null,null,293,970,null,802,688,504,344,971,889,749,793,null,null,null,null,678,null,781,null,null,368,437,null,null,921,779,null,null,null,null,null,942,909,804,null,727,null,null,null,null,886,828,null,null,693,532,null,null,null,null,null,null,336,420,null,549,434,316,564,null,599,746,null,818,null,null,null,null,424,null,803,null,null,null,null,531,876,891,873,761,null,null,890,null,null,null,null,null,null,null,null,null,617,464,null,903,615,581,376,395,330,496,234,321,null,null,null,975,null,null,null,null,null,null,null,null,null,null,null,null,630,null,null,null,248,null,659,359,null,null,null,null,null,null,null,986,null,null,819,805,null,948,538,572,null,null,null,null,null,null,742,null,null,null,null,244,null,136,null,545,null,428,418,807,null,null,null,314,null,855,null,null,null,614,996,null,null,999,null,865,null,null,null,406,null,567,527,null,null,611,null,717,null,null,null,null,null,481,null,null,816,null,713,809,null,701,null,563,null,null,940,null,null,null,null,null,852,null,null,955,null,null,null,null,null,null,null,917,null,null,null,null,910,null,null,821,null,924,null,null,null,702,691,661,569,554,null,505,null,null,520,782,470,510,null,null,null,null,null,null,823,null,526,null,null,null,672,711,null,null,null,null,null,914,null,null,null,null,684,null,null,588,947,null,863,null,null,null,925,585,462,null,488,528,null,null,973,273,null,343,null,null,838,null,849,637,null,696,null,530,null,null,null,null,null,null,980,null,880,null,null,582,null,null,null,322,148,329,602,762,560,null,null,719,null,null,393,411,null,null,722,877,null,null,null,null,null,null,null,null,null,783,null,738,699,null,962,null,509,680,997,null,747,754,931,941,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,770,null,null,null,808,799,null,null,899,689,516,null,null,830,null,null,null,null,587,832,888,null,870,null,null,null,null,null,null,null,744,null,954,null,null,null,null,null,null,null,810,698,960,840,723,null,null,null,null,392,354,518,621,897,null,null,null,null,null,null,872,null,null,null,null,null,null,959,658,467,366,394,306,null,404,648,null,null,866,null,null,null,728,476,432,957,null,null,874,null,null,null,null,817,null,null,714,null,null,null,null,801,null,null,null,826,788,null,null,null,961,null,null,null,null,null,null,null,null,968,null,898,null,645,null,null,null,845,null,null,null,null,null,null,null,null,766,null,null,929,944,null,null,null,null,null,null,null,null,763,null,576,null,700,609,null,null,935,916,null,null,null,null,666,null,null,null,427,null,null,null,360,384,906,489,663,682,null,null,771,null,512,null,902,null,null,null,null,null,null,827,null,null,null,null,null,null,null,null,null,null,null,null,null,939,null,814,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,620,null,null,null,null,null,756,669,591,null,null,589,601,null,null,759,null,989,831,885,null,null,926,null,null,null,null,null,951,null,null,null,null,null,null,null,919,null,null,647,null,987,597,null,null,null,null,null,null,915,842,null,null,null,null,null,null,null,null,null,null,null,null,null,786]
[138,749,845,604,34,894,233,347,208,983,924,444,692,307,220,454,494,739,595,682,952,1,743,528,256,5,447,88,74,550,62,653,297,145,437,158,937,378,581,568,130,241,46,708,452,17,154,815,77,476,903,322,338,229,567,549,630,850,21,941,187,654,724,562,261,827,313,360,450,267,59,900,139,28,240,824,823,245,814,403,366,148,247,893,53,936,271,527,221,762,940,314,711,490,968,491,720,746,734,429,388,131,433,457,971,934,854,740,231,419,372,830,560,215,81,377,607]

-->