1. 题目解析
题目链接:814. 二叉树剪枝
这个问题的理解其实相当简单,只需看一下示例,基本就能明白其含义了。
2.算法原理
想象一下,你有一堆层层叠叠的积木,你想从底部开始,把那些标记为0的积木拿走。如果直接从上面开始拿,你可能会碰到很多麻烦,因为你不知道下面的积木长什么样,也不敢轻易动它们。但是,如果你从最下面的积木开始,一层一层往上拿,事情就变得简单多了。
这就像我们处理二叉树一样。如果从上往下删除节点,我们就需要知道左右子树的情况,这确实是个头疼的问题。但反过来,如果我们从下往上,也就是从最底层的叶子节点开始,删除那些值为0的叶子节点,然后再处理上一层,这样问题就简单多了。
具体来说,我们可以采用后序遍历的方法。后序遍历就是先处理左子树,再处理右子树,最后处理当前节点。当我们处理到当前节点时,只要判断它是不是叶子节点,并且值是不是0,如果是的话,就直接删除它。
不过要注意,当我们删除一个叶子节点后,它的父节点可能就变成新的叶子节点了。所以,处理完当前节点后,我们还需要检查它的父节点是否需要处理。这就是为什么我们选择后序遍历的原因,因为后序遍历最先遍历到的总是叶子节点。
算法流程可以这样描述:
-
定义一个递归函数:
dfs(TreeNode*& root)
,这个函数会检查当前节点是否需要删除。 -
递归的出口:如果传入的节点为空,那么直接返回,不需要做任何处理。
-
递归处理左右子树:先调用
dfs
函数处理左子树,再处理右子树。 -
处理当前节点:
- 判断当前节点是否已经是叶子节点(即左右子节点都被删除了),并且节点的值为0。
- 如果是的话,就删除这个节点。
- 如果不是,就保持原样,不做任何处理。
通过这样的方式,我们可以从底部开始,逐步删除值为0的叶子节点,并且保证删除后的树仍然满足我们的要求。当所有的叶子节点都被检查并处理完毕后,如果它们的值都是1,那就说明整棵树都包含1,此时我们就可以返回结果了。
这种方法的好处是,它让删除操作变得相对简单,而且不会影响最终的结果。就像我们一层一层地拿走积木,最后留下的都是我们想要的。
3.代码编写
/**
* 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);
if(root->left == nullptr && root->right == nullptr && root->val == 0)
{
delete root;
root = nullptr;
}
return root;
}
};
The Last
嗯,就是这样啦,文章到这里就结束啦,真心感谢你花时间来读。
觉得有点收获的话,不妨给我点个赞吧!
如果发现文章有啥漏洞或错误的地方,欢迎私信我或者在评论里提醒一声~