1. 題目

給出二叉樹的根節(jié)點(diǎn) root，樹上每個(gè)節(jié)點(diǎn)都有一個(gè)不同的值。

如果節(jié)點(diǎn)值在 to_delete 中出現(xiàn)，我們就把該節(jié)點(diǎn)從樹上刪去，最后得到一個(gè)森林（一些不相交的樹構(gòu)成的集合）。

返回森林中的每棵樹。你可以按任意順序組織答案。

示例：

輸入：root = [1,2,3,4,5,6,7], to_delete = [3,5] 輸出：[[1,2,null,4],[6],[7]]提示： 樹中的節(jié)點(diǎn)數(shù)最大為 1000。 每個(gè)節(jié)點(diǎn)都有一個(gè)介于 1 到 1000 之間的值，且各不相同。 to_delete.length <= 1000 to_delete 包含一些從 1 到 1000、各不相同的值。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/delete-nodes-and-return-forest
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

2. 解題

• 要?jiǎng)h除的放入哈希表，方便快速查找
• 遞歸遍歷，記錄父節(jié)點(diǎn)，和左右方向
• 如果要?jiǎng)h除，斷開父節(jié)點(diǎn)，子節(jié)點(diǎn)，遍歷子節(jié)點(diǎn)
• 不刪除，且父節(jié)點(diǎn)為空，加入答案

class Solution {unordered_set<int> s;vector<TreeNode*> ans; public:vector<TreeNode*> delNodes(TreeNode* root, vector<int>& to_delete) {if(!root)return {};for(int del : to_delete)s.insert(del);//哈希快速查找order(root, NULL, 0);return ans;}void order(TreeNode* root, TreeNode* father, int dir){ //參數(shù)，當(dāng)前節(jié)點(diǎn)，其父節(jié)點(diǎn)，是父節(jié)點(diǎn)的左節(jié)點(diǎn)還是右節(jié)點(diǎn)if(!root)return;if(s.count(root->val))//root需要?jiǎng)h除{if(father)//要?jiǎng)h除的節(jié)點(diǎn)有父節(jié)點(diǎn){if(dir==0)//是左邊過來的father->left = NULL;//斷開與父節(jié)點(diǎn)的鏈接elsefather->right = NULL;}TreeNode *l = root->left, *r = root->right;//當(dāng)前節(jié)點(diǎn)的左右子節(jié)點(diǎn)root->left = NULL;//斷開子的鏈接root->right = NULL;//斷開子的鏈接order(l, NULL, 0);//遍歷左子，其父節(jié)點(diǎn)斷開了，為空，第三個(gè)參數(shù)隨意order(r, NULL, 0);//遍歷右子}else//root不用刪除{if(!father)//如果沒有父節(jié)點(diǎn)了,新的樹根，加入答案ans.push_back(root);order(root->left, root, 0);//遍歷左子，第三個(gè)參數(shù)0表示左order(root->right, root, 1);//遍歷右子，第三個(gè)參數(shù)1表示右}} };

總結(jié)

以上是生活随笔為你收集整理的LeetCode 1110. 删点成林（二叉树递归）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。