题目描述
给定一个二叉树 根节点 root ,树的每个节点的值要么是 0,要么是 1。请剪除该二叉树中所有节点的值为 0 的子树。 节点 node 的子树为 node 本身,以及所有 node 的后代。
LCR 047. 二叉树剪枝 - 力扣(LeetCode)
剪除二叉树中所有节点值为0的子树,意味着我们需要删除为零的叶子节点。我们可以通过递归地遍历树来解决该问题。
递归思路讲解:
-
定义递归函数:
首先,我们需要定义一个递归函数pruneTree
,它接受一个TreeNode*
类型的参数(指向二叉树根节点的指针),并返回一个TreeNode*
类型的结果(剪除后的根节点指针)。 -
基本情况:
递归函数需要有一个基本情况来结束递归。在这个问题中,基本情况是当当前节点为空时(即root == nullptr
),我们直接返回nullptr
,表示没有子树需要剪除。 -
递归步骤:
- 处理左子树:在递归函数中,我们首先递归地调用
pruneTree
来处理当前节点的左子树。这意味着我们会深入左子树,直到遇到空节点或需要剪除的节点为止。 - 处理右子树:同样地,我们递归地调用
pruneTree
来处理当前节点的右子树。 - 更新当前节点:在递归地处理了左子树和右子树之后,我们检查当前节点的值。如果当前节点的值为0,我们将其左子树和右子树都置为
nullptr
(并可选地释放内存),然后返回nullptr
来表示这个节点及其子树应该被剪除。如果当前节点的值不为0,我们保留这个节点并返回它。
- 处理左子树:在递归函数中,我们首先递归地调用
-
组合结果:
递归的魔力在于它能够自动地将子问题的结果组合成原问题的解。在这个问题中,当我们递归地处理完左子树和右子树后,我们自动地得到了剪除后的子树,并将它们连接回当前节点(如果当前节点不应该被剪除的话)。 -
递归的终止:
递归的终止是由基本情况来保证的。在这个问题中,当遇到空节点时,递归就会终止。此外,由于我们是在后序遍历(先处理子节点再处理父节点)的顺序中递归地剪除子树,所以当我们返回到父节点时,它的子树已经被正确地剪除了。 -
返回结果:
最后,递归函数返回剪除后的根节点指针。这个指针可能指向原始的根节点(如果根节点不应该被剪除的话),也可能指向一个新的根节点(如果原始的根节点被剪除了,并且它的某个子节点成为了新的根节点)。在实际应用中,我们通常会忽略这个返回值(除非我们需要进一步处理剪除后的树),因为递归地修改树本身就已经达到了我们的目的。
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;
}};