每日OJ题_二叉树dfs③_力扣814. 二叉树剪枝-Toy模板网

这篇具有很好参考价值的文章主要介绍了每日OJ题_二叉树dfs③_力扣814. 二叉树剪枝。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

力扣814. 二叉树剪枝

解析代码

力扣814. 二叉树剪枝

814. 二叉树剪枝

难度中等

给你二叉树的根结点 root ，此外树的每个结点的值要么是 0 ，要么是 1 。

返回移除了所有不包含 1 的子树的原二叉树。

节点 node 的子树为 node 本身加上所有 node 的后代。

示例 1：

每日OJ题_二叉树dfs③_力扣814. 二叉树剪枝,每日OJ题,深度优先,leetcode,剪枝,c++,算法,dfs,回归算法

输入：root = [1,null,0,0,1]
输出：[1,null,0,null,1]
解释：
只有红色节点满足条件“所有不包含 1 的子树”。 右图为返回的答案。

示例 2：

每日OJ题_二叉树dfs③_力扣814. 二叉树剪枝,每日OJ题,深度优先,leetcode,剪枝,c++,算法,dfs,回归算法

输入：root = [1,0,1,0,0,0,1]
输出：[1,null,1,null,1]

示例 3：

每日OJ题_二叉树dfs③_力扣814. 二叉树剪枝,每日OJ题,深度优先,leetcode,剪枝,c++,算法,dfs,回归算法

输入：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，就剪掉。文章来源地址https://www.toymoban.com/news/detail-835615.html

/**
 * 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;
    }
};

到了这里，关于每日OJ题_二叉树dfs③_力扣814. 二叉树剪枝的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！