【力扣刷题实战】二叉树剪枝

大家好，我是小卡皮巴拉

文章目录

目录

力扣题目：二叉树剪枝

题目描述

解题思路

问题理解

算法选择

具体思路

解题要点

完整代码（C++）

兄弟们共勉 ！！！ 

---

每篇前言

博客主页：小卡皮巴拉

咱的口号：🌹小比特，大梦想🌹

作者请求：由于博主水平有限，难免会有错误和不准之处，我也非常渴望知道这些错误，恳请大佬们批评斧正。

力扣题目：二叉树剪枝

原题链接：814. 二叉树剪枝 - 力扣（LeetCode）

题目描述

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

解题思路

问题理解

本题给定一个二叉树，树中每个节点的值为 0 或 1 。要求移除所有不包含 1 的子树，即如果一个子树（包括节点本身及其所有后代）中所有节点的值都为 0，则将该子树从原二叉树中移除。

算法选择

采用递归算法。因为二叉树的结构本身具有递归的性质，通过递归地检查每个子树是否满足移除条件，并对满足条件的子树进行移除操作，可以很自然地解决这个问题。

具体思路

1. 递归终止条件：检查当前节点 root 是否为空。如果为空，直接返回空指针，表示当前子树不存在，不需要进行任何操作。

2. 递归修剪子树：

   • 对当前节点的左子树进行递归修剪，即 root->left = pruneTree(root->left)。这一步会返回修剪后的左子树，将其赋值给当前节点的左指针。

   • 对当前节点的右子树进行递归修剪，即 root->right = pruneTree(root->right)。同样，返回的修剪后的右子树会赋值给当前节点的右指针。

3. 判断并移除子树：检查当前节点是否为叶子节点（即 root->left == nullptr && root->right == nullptr）且值为 0。如果是，说明当前子树是一个所有节点值都为 0 的子树，需要将其移除。通过 delete root 释放当前节点的内存（防止内存泄漏），并将 root 设为空指针。

4. 返回结果：返回修剪后的当前节点。如果当前节点没有被移除，返回的就是当前节点本身；如果当前节点被移除了（即 root 为空指针），则返回空指针。

解题要点

1. 递归的运用：正确实现递归函数，对二叉树的每个子树进行递归修剪，确保能够遍历整棵树。

2. 子树移除条件的判断：准确判断一个子树是否为所有节点值都为 0 的子树，即判断当前节点是否为叶子节点且值为 0。

3. 内存管理：在移除节点时，要注意释放节点的内存，防止内存泄漏。通过 delete root 操作来释放内存，并将指针设为空。

完整代码（C++）

/*** 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) {// 如果当前节点为空，直接返回空指针，表示当前子树不存在if(root == nullptr) return nullptr;// 递归地修剪当前节点的左子树，并将修剪后的左子树赋值给当前节点的左指针root->left = pruneTree(root->left);// 递归地修剪当前节点的右子树，并将修剪后的右子树赋值给当前节点的右指针root->right = pruneTree(root->right);// 判断当前节点是否为叶子节点（即没有左子节点和右子节点）且值为 0if(root->left == nullptr && root->right == nullptr && root->val == 0){// 如果是，删除当前节点以释放内存（防止内存泄漏）delete root;// 将当前节点指针设为空，表明该节点已被移除root = nullptr;}// 返回修剪后的当前节点（可能为空，也可能是修剪后的子树的根节点）return root;}
};

兄弟们共勉 ！！！ 

码字不易，求个三连

抱拳了兄弟们！