春意盎然，适合“二叉树剪枝”
一起养成写作习惯！这是我参与「掘金日新计划 · 4 月更文挑战」的第3天，点击查看活动详情。
清明假期第 1 天，日日新更文继续 ^_^
天气正好，树木繁茂，不如来道二叉树的 —— 二叉树剪枝 题~🐶
18a0d46f5c8a41acee068890f05f854.jpg
题：
给你二叉树的根结点 root ，此外树的每个结点的值要么是 0 ，要么是 1 。
返回移除了所有不包含 1 的子树的原二叉树。
节点 node 的子树为 node 本身加上所有 node 的后代。
image.png
示例 1：
输入：root = [1,null,0,0,1]
输出：[1,null,0,null,1]
解释：
只有红色节点满足条件“所有不包含 1 的子树”。 右图为返回的答案。
image.png
示例 2：
输入：root = [1,0,1,0,0,0,1]
输出：[1,null,1,null,1]
image.png
示例 3：
输入：root = [1,1,0,1,1,0,1,0]
输出：[1,1,0,1,1,null,1]【解题思路】
题目要求剪除二叉树中所有节点的值为 0 的子树，那么怎么知道当前二叉树所有节点的值为0，使用后序遍历无疑了； 递归只需要考虑当前节点需要做什么事情，当前节点能否被剪枝取决于左右子树及当前节点的值；
这道题的难点在于要一直剪枝，直到没有值为 0 的叶子节点为止，只有从后序遍历位置自底向上处理才能获得最高的效率。
【JS 实现】
/**
* @param {TreeNode} root
* @return {TreeNode}
*/
var pruneTree = function(root) {
// 判断非空情况
if (root == null) {
return root;
}
root.left = pruneTree(root.left);
root.right = pruneTree(root.right);
// 当左右节点都为空且当前节点的值为0的情况下，即可剪枝
if (!root.left && !root.right && root.val == 0) {
return null;
}
return root;
};【验证】
image.png
后序遍历+递归，简单实现，赞👍
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2022-04-03，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
