春意盎然,适合“二叉树剪枝”

简介: 给你二叉树的根结点 root ,此外树的每个结点的值要么是 0 ,要么是 1 。返回移除了所有不包含 1 的子树的原二叉树。节点 node 的子树为 node 本身加上所有 node 的后代。

image.png

题:

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

后序遍历+递归,简单实现,赞👍



相关文章
|
存储 前端开发 测试技术
DDD - 六边形架构和CQRS架构
DDD - 六边形架构和CQRS架构
2134 0
|
人工智能 算法 C语言
C语言算法---求鞍点
题目:有一个3X4矩阵,要求输出其鞍点(行列均最大的值),以及它的行号和列号。 int a[3][4] = {{123,94,-10,218},                          {3,9,10,-83},                        ...
1273 0
|
6天前
|
人工智能 JSON API
全网刷屏的 Jev 模型正式开放!一手实战测评 + 保姆级教程
全网爆火的 Jev 模型是什么?有什么用?怎么使用?怎么接入 AI 编程工具?效果真的好么?傻子可懂的 Jev 保姆级实战教程 + 项目实战测评来啦
6646 8
|
5天前
|
人工智能 测试技术 API
最近全网爆火的 Jev 到底是什么?适合干什么、怎么用,一篇讲透!
Jev是TypeSafe AI推出的“系统一模型”,不生成文本,专做毫秒级结构化决策:Choice(多选)、Score(打分)、Noul(是非概率)。响应快193倍、成本低444倍,适合工单路由、内容审核、测试定级等高频判断场景。
1308 4
最近全网爆火的 Jev 到底是什么?适合干什么、怎么用,一篇讲透!
|
5天前
|
人工智能 并行计算 PyTorch
秋叶 ComfyUI 2026 整合包 v3.2 完整部署教程:Python 3.13 + Torch 2.13 全栈升级
秋叶aaaki ComfyUI 2026年8月整合包v3.2正式发布!全面升级Python 3.13.11、PyTorch 2.13.0+cu130及ComfyUI v0.30.2,原生支持MiniMax H3、Wan 2.2、Qwen-Image-2.1等2026主流音视频/图像模型,解压即用,无需环境配置。
762 5
|
19天前
|
人工智能 自然语言处理 安全
阿里云千问办公 QwenWork详细介绍:产品核心能力、典型场景、价格及常见问题解答
千问办公是阿里云推出的一站式AI办公平台,主打"不止于对话,更注重交付",依托通义千问旗舰大模型,用户一句话即可完成数据分析、PPT生成、视频剪辑等复杂任务,直接输出可用成果。产品深度打通钉钉生态与企业OA,覆盖桌面端、网页端,提供企业标准版198元/人/月等多档订阅方案,新用户注册即赠2000积分,适配工程师、HR、财务等多职业办公场景,成为能动手干活的"全能AI同事"。
3390 10
|
13天前
|
缓存 IDE Java
【保姆级】Android Studio下载、安装和汉化教程(2026最新)
Android Studio 是 Google 官方推出的免费 Android 应用开发集成环境,基于 IntelliJ IDEA,内置模拟器、调试器、性能分析及 Compose 界面工具,功能全面,文档丰富,是安卓开发首选工具。(239字)
1466 1
|
17天前
|
IDE 开发工具
Qoder 上线 Sonus 模型,Computer Use 能力全面增强
Qoder国际版上线全新内置大模型Sonus(/ˈsoʊnəs/),全球领先,专精超长任务执行与电脑操作(Computer Use)。配合Qoder桌面端0.2.3版本,可自主完成编程、金融建模、科研及表格制作等复杂工作。现全面支持Qoder全系产品,效率提升3.2倍。
1875 9
Qoder 上线 Sonus 模型,Computer Use 能力全面增强

热门文章

最新文章