每日OJ题_二叉树dfs③_力扣814. 二叉树剪枝

目录

力扣814. 二叉树剪枝

解析代码

---

力扣814. 二叉树剪枝

814. 二叉树剪枝

难度 中等

给你二叉树的根结点 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;
    }
};