策划与设计一个电子商务网站,提高wordpress打开速度,wordpress电商ar,网站常用的字体给定一个二叉树 根节点 root #xff0c;树的每个节点的值要么是 0#xff0c;要么是 1。请剪除该二叉树中所有节点的值为 0 的子树。节点 node 的子树为 node 本身#xff0c;以及所有 node 的后代。 示例 1:
输入: [1,null,0,0,1]
输出: [1,null,0,null,1]
解释:
只有红…给定一个二叉树 根节点 root 树的每个节点的值要么是 0要么是 1。请剪除该二叉树中所有节点的值为 0 的子树。节点 node 的子树为 node 本身以及所有 node 的后代。 示例 1:
输入: [1,null,0,0,1]
输出: [1,null,0,null,1]
解释:
只有红色节点满足条件“所有不包含 1 的子树”。
右图为返回的答案。 示例 2:
输入: [1,0,1,0,0,0,1]
输出: [1,null,1,null,1]
解释: 示例 3:
输入: [1,1,0,1,1,0,1,0]
输出: [1,1,0,1,1,null,1]
解释: 1解法一
class Solution {
public:bool dfs(TreeNode* node) {if(nodenullptr) return false;bool left dfs(node-left);bool right dfs(node-right);// 叶子节点且值为0 执行删除if(leftfalse rightfalse node-val 0) return false;// 非叶子节点左孩子返回false将其删除具体操作为node-left nullptrif(leftfalse) node-left nullptr;// 非叶子节点右孩子返回false将其删除具体操作为node-right nullptrif(rightfalse) node-right nullptr; return true;}TreeNode* pruneTree(TreeNode* root) {return dfs(root)?root:nullptr;}
}; 2解法二
class Solution {
public:int dfs(TreeNode* node) {if(nodenullptr) return 0;int left dfs(node-left);int right dfs(node-right);if(left0) node-leftnullptr;if(right0) node-rightnullptr;return leftrightnode-val;}TreeNode* pruneTree(TreeNode* root) {int ans dfs(root);if(ans0) return nullptr;return root;}
};
3解法三
class Solution {
public:TreeNode* pruneTree(TreeNode* root) {if(root nullptr) return nullptr;root-left pruneTree(root-left);root-right pruneTree(root-right);if(root-leftnullptr root-rightnullptr root-val 0) { // 如果叶子节点的值为0就删除该节点return nullptr;}return root;}
}; leetCode 1110. 删点成林 1110. 删点成林 - 力扣LeetCode
给出二叉树的根节点 root树上每个节点都有一个不同的值。如果节点值在 to_delete 中出现我们就把该节点从树上删去最后得到一个森林一些不相交的树构成的集合。返回森林中的每棵树。你可以按任意顺序组织答案。
示例 1 输入root [1,2,3,4,5,6,7], to_delete [3,5]
输出[[1,2,null,4],[6],[7]]示例 2
输入root [1,2,4,null,3], to_delete [3]
输出[[1,2,4]] 解法一“递归”的思路可以分为「递」和「归」两个部分。
「递」的思路向下传参然后不断进行处理类似前序遍历「归」的思路先遍历到底然后向上传参类似后序遍历
本题中采用「归」的思路需要解决两个问题
1.向上传递的参数是什么2.在当前节点如何进行处理
思路和分析
1.如果该节点(node)不需要被删除那么返回 node 即可如果需要被删除那么返回 null 即可2.在处理需要被删除的节点node时删除前先判断其有无左右子树若有就将其左右子树加入ans中再返回 null 即可 class Solution {
public:vectorTreeNode * ans;unordered_setint delSet;bool dfs(TreeNode *node) {if(nodenullptr) return false;bool left dfs(node-left);bool right dfs(node-right);if(delSet.count(node-val)) {if(left) ans.push_back(node-left);if(right) ans.push_back(node-right);return false;}if(leftfalse) node-left nullptr;if(rightfalse) node-right nullptr; return node;}vectorTreeNode * delNodes(TreeNode *root, vectorint to_delete) {for(const auto a:to_delete) {delSet.insert(a);}if (dfs(root)) ans.push_back(root);return ans;}
};
解法二
class Solution {
public:vectorTreeNode * ans;unordered_setint delSet;TreeNode * dfs(TreeNode *node) {if(nodenullptr) return nullptr;node-left dfs(node-left);node-right dfs(node-right);if(delSet.count(node-val)) {if(node-left) ans.push_back(node-left);if(node-right) ans.push_back(node-right);return nullptr; // 相当于删除节点}return node;// 没有删除}vectorTreeNode * delNodes(TreeNode *root, vectorint to_delete) {for(const auto a:to_delete) {delSet.insert(a);}if (dfs(root)) ans.push_back(root);return ans;}
};
解法三来自灵茶山艾府的题解和解法二思路差不多文字总结来自灵神的文章1110. 删点成林 - 力扣LeetCodehttps://leetcode.cn/problems/delete-nodes-and-return-forest/solutions/2289131/he-shi-ji-lu-da-an-pythonjavacgo-by-endl-lpcd/
class Solution {vectorTreeNode * ans;unordered_setint s;TreeNode *dfs(TreeNode *node) {if (node nullptr) return nullptr;node-left dfs(node-left);node-right dfs(node-right);if (!s.count(node-val)) return node;if (node-left) ans.push_back(node-left);if (node-right) ans.push_back(node-right);return nullptr;}public:vectorTreeNode * delNodes(TreeNode *root, vectorint to_delete) {for (int x: to_delete) s.insert(x);if (dfs(root)) ans.push_back(root);return ans;}
};
总结考虑清楚两个点 1.对叶子节点被删如何处理直接丢掉节点 2.对非叶子节点被删如何处理把子节点加入结果当前节点丢掉即可
最后判断树根是否为空非空则加入ans
推荐和参考文章
1110. 删点成林 - 力扣LeetCodehttps://leetcode.cn/problems/delete-nodes-and-return-forest/solutions/2289131/he-shi-ji-lu-da-an-pythonjavacgo-by-endl-lpcd/1110. 删点成林 - 力扣LeetCodehttps://leetcode.cn/problems/delete-nodes-and-return-forest/solutions/2289170/er-cha-shu-de-hou-xu-bian-li-cong-xia-wa-0y4l/1110. 删点成林 - 力扣LeetCodehttps://leetcode.cn/problems/delete-nodes-and-return-forest/solutions/2289224/shan-dian-cheng-lin-cai-yong-di-gui-zhon-9jsj/
