目录
难度 中等
给你二叉树的根结点 root
,此外树的每个结点的值要么是 0
,要么是 1
。
返回移除了所有不包含 1
的子树的原二叉树。
节点 node
的子树为 node
本身加上所有 node
的后代。
示例 1:
输入:root = [1,null,0,0,1] 输出:[1,null,0,null,1] 解释: 只有红色节点满足条件“所有不包含 1 的子树”。 右图为返回的答案。
示例 2:
输入:root = [1,0,1,0,0,0,1] 输出:[1,null,1,null,1]
示例 3:
输入:root = [1,1,0,1,1,0,1,0] 输出:[1,1,0,1,1,null,1]
提示:
[1, 200]
内Node.val
为 0
或 1
- /**
- * 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:
- TreeNode* pruneTree(TreeNode* root) {
-
- }
- };
题意就是删除所有元素只有0的子树,解题思路就是递归+后序遍历:
相信递归一定能把左右子树都剪枝了,出口是碰到叶子结点,函数体是如果这个结点的左结点和右结点都为空,并且值为0,就剪掉。
- /**
- * 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:
- TreeNode* pruneTree(TreeNode* root) {
- /*
- 题意就是删除所有元素只有0的子树,解题思路就是递归+后序遍历:
- 相信递归一定能把左右子树都剪枝了,出口是碰到叶子结点,
- 函数体是如果这个结点的左结点和右结点都为空,并且值为0,就剪掉。
- */
- if(root == nullptr)
- return nullptr;
-
- root->left = pruneTree(root->left);
- root->right = pruneTree(root->right);
-
- if(root->left == nullptr && root->right == nullptr && root->val == 0)
- {
- delete root; // 可加可不加,面试时可以问结点是不是new出来的,不然会报错
- root = nullptr;
- }
- return root;
- }
- };