欢迎来到尧图网

客户服务 关于我们

您的位置:首页 > 房产 > 建筑 > 二叉树剪枝

二叉树剪枝

2025/9/26 20:56:27 来源:https://blog.csdn.net/2302_80190174/article/details/143560302  浏览:    关键词:二叉树剪枝

题目描述

给定一个二叉树 根节点 root ,树的每个节点的值要么是 0,要么是 1。请剪除该二叉树中所有节点的值为 0 的子树。 节点 node 的子树为 node 本身,以及所有 node 的后代。

LCR 047. 二叉树剪枝 - 力扣(LeetCode)

剪除二叉树中所有节点值为0的子树,意味着我们需要删除为零的叶子节点。我们可以通过递归地遍历树来解决该问题。

递归思路讲解:

  1. 定义递归函数
    首先,我们需要定义一个递归函数pruneTree,它接受一个TreeNode*类型的参数(指向二叉树根节点的指针),并返回一个TreeNode*类型的结果(剪除后的根节点指针)。

  2. 基本情况
    递归函数需要有一个基本情况来结束递归。在这个问题中,基本情况是当当前节点为空时(即root == nullptr),我们直接返回nullptr,表示没有子树需要剪除。

  3. 递归步骤

    • 处理左子树:在递归函数中,我们首先递归地调用pruneTree来处理当前节点的左子树。这意味着我们会深入左子树,直到遇到空节点或需要剪除的节点为止。
    • 处理右子树:同样地,我们递归地调用pruneTree来处理当前节点的右子树。
    • 更新当前节点:在递归地处理了左子树和右子树之后,我们检查当前节点的值。如果当前节点的值为0,我们将其左子树和右子树都置为nullptr(并可选地释放内存),然后返回nullptr来表示这个节点及其子树应该被剪除。如果当前节点的值不为0,我们保留这个节点并返回它。
  4. 组合结果
    递归的魔力在于它能够自动地将子问题的结果组合成原问题的解。在这个问题中,当我们递归地处理完左子树和右子树后,我们自动地得到了剪除后的子树,并将它们连接回当前节点(如果当前节点不应该被剪除的话)。

  5. 递归的终止
    递归的终止是由基本情况来保证的。在这个问题中,当遇到空节点时,递归就会终止。此外,由于我们是在后序遍历(先处理子节点再处理父节点)的顺序中递归地剪除子树,所以当我们返回到父节点时,它的子树已经被正确地剪除了。

  6. 返回结果
    最后,递归函数返回剪除后的根节点指针。这个指针可能指向原始的根节点(如果根节点不应该被剪除的话),也可能指向一个新的根节点(如果原始的根节点被剪除了,并且它的某个子节点成为了新的根节点)。在实际应用中,我们通常会忽略这个返回值(除非我们需要进一步处理剪除后的树),因为递归地修改树本身就已经达到了我们的目的。

class Solution {
public:TreeNode* pruneTree(TreeNode* root) {// 基本情况:如果节点为空,返回nullptrif (root == nullptr) {return nullptr;}// 递归地剪除左子树和右子树root->left = pruneTree(root->left);root->right = pruneTree(root->right);// 检查当前节点的值if (root->val == 0) {// 如果当前节点值为0,返回nullptr表示删除该节点return nullptr;}// 否则返回当前节点return root;
}};

 

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

热搜词