当前位置: 首页 > news >正文

计算布尔二叉树的值

给你一棵 完整二叉树 的根节点,这棵树有以下特征:

  • 叶子节点 要么值为 0 要么值为 1 ,其中 0 表示 False ,1 表示 True 。
  • 非叶子节点 要么值为 2 要么值为 3 ,其中 2 表示逻辑或 OR ,3 表示逻辑与 AND 。

计算 一个节点的值方式如下: 如果节点是个叶子节点,那么节点的 值 为它本身,即 True 或者 False 。 否则,计算 两个孩子的节点值,然后将该节点的运算符对两个孩子值进行 运算 。 返回根节点 root 的布尔运算值。

  • 完整二叉树 是每个节点有 0 个或者 2 个孩子的二叉树。
  • 叶子节点 是没有孩子的节点。

2331. 计算布尔二叉树的值 - 力扣(LeetCode)

解题思路

递归是解决这个问题的一个关键部分。在二叉树的相关问题中,递归经常被用来遍历树结构,因为它允许我们在不显式使用栈或队列的情况下,通过函数调用栈隐式地维护一个访问节点的顺序。

  1. 定义节点结构
    使用TreeNode结构来表示树的节点,包含节点的值和左右孩子指针。

  2. 递归遍历
    使用递归函数遍历树的节点。对于每个节点,根据其值判断是叶子节点还是非叶子节点,并分别处理。

  3. 逻辑运算

    • 如果节点是叶子节点(值为0或1),直接返回对应的布尔值。
    • 如果节点是非叶子节点,根据其值(2或3)分别进行逻辑或和逻辑与运算,并返回结果。
bool evaluateTree(TreeNode* root) {  // 基本情况(叶子节点)  if (root->val == 0) {  return false;  } else if (root->val == 1) {  return true;  }  // 递归情况(非叶子节点)  // 对于非叶子节点,我们需要计算其左右孩子的值  bool leftValue = evaluateTree(root->left);  // 递归调用,计算左孩子的值  bool rightValue = evaluateTree(root->right); // 递归调用,计算右孩子的值  // 根据当前节点的运算符(由 val 决定),返回相应的逻辑运算结果  if (root->val == 2) {  // 当前节点是逻辑或 OR 运算符  return leftValue || rightValue;  } else if (root->val == 3) {  // 当前节点是逻辑与 AND 运算符  return leftValue && rightValue;  }  // 理论上不会执行到这里,因为题目已经限定节点值只能是0, 1, 2, 3  // 但为了代码的健壮性,最好还是加上这个返回语句  return false; // 这是一个默认返回,实际上不会被执行  
}

 递归的拆解

  1. 基本情况
    • 当我们遇到一个叶子节点时(即节点的值为0或1),我们不需要再递归调用,因为叶子节点没有孩子。我们直接返回该节点的布尔值(0对应false,1对应true)。
  2. 递归情况
    • 当我们遇到一个非叶子节点时(即节点的值为2或3),我们需要计算其左右孩子的值。
    • 我们通过递归调用evaluateTree函数来计算左孩子的值(leftValue)和右孩子的值(rightValue)。
    • 在递归调用中,我们实际上是在处理一个更小的子问题:计算一个子树的根节点的布尔值。
    • 递归调用会继续进行,直到我们遇到叶子节点为止。一旦我们到达叶子节点,递归就会开始回溯,每个递归调用都会返回一个布尔值给它的调用者。
  3. 回溯
    • 在回溯过程中,我们根据当前节点的运算符(2或3)和左右孩子的值(leftValuerightValue)来计算当前节点的布尔值。
    • 然后,这个值会被返回给当前节点的父节点的递归调用。
  4. 终止
    • 递归会在所有叶子节点都被访问并处理完毕后终止。由于树是有限的,递归调用最终会耗尽所有的节点,并返回到最初的调用点(即根节点的递归调用)。
  5. 结果
    • 最终,根节点的递归调用会返回一个布尔值,这个值就是整个树的逻辑运算结果。

注意事项

  • 递归函数必须有一个明确的终止条件(基本情况),否则会导致无限递归和栈溢出。
  • 在递归调用中,我们实际上是在将问题分解成更小的子问题来解决。
  • 递归的关键在于理解函数调用的栈行为,以及每个递归调用如何与它的子调用和父调用相关联。

相关文章:

计算布尔二叉树的值

给你一棵 完整二叉树 的根节点,这棵树有以下特征: 叶子节点 要么值为 0 要么值为 1 ,其中 0 表示 False ,1 表示 True 。非叶子节点 要么值为 2 要么值为 3 ,其中 2 表示逻辑或 OR ,3 表示逻辑与 AND 。 …...

Java-I/O框架09:InputStreamReader、OutputStreamWriter使用

视频链接:16.24 转换流的使用_哔哩哔哩_bilibilihttps://www.bilibili.com/video/BV1Tz4y1X7H7?spm_id_from333.788.videopod.episodes&vd_sourceb5775c3a4ea16a5306db9c7c1c1486b5&p24 1.InputStreamReader使用 package com.yundait.Demo05;import java…...

二十九、Python基础语法(继承-上)

一、概念介绍 继承:继承描述的是类与类之间的关系,集成之后子类对象可以直接使用父类中定义的方法的属性,可以减少代码冗余,提高编码效率。 二、继承语法 三、继承例子 # 定义一个父类 Animal class Animal:def __init__(self,…...

JVM 复习1

内容 JVM 类加载器 JVM 运行时数据区 测试1 JVM整体架构考察。整体架构分为哪三层。分别是什么?通过绘制架构图来作答。 前端编译器是什么,作用是什么。要进行那些步骤? 类加载构成几个步骤。并且详细作答每个步骤的工作。 准备阶段和初…...

安装fpm,解决*.deb=> *.rpm

要从生成 .deb 包转换为 .rpm 包,可以按照以下步骤修改打包脚本 1. 使用 fpm 工具 fpm 是一个强大的跨平台打包工具,可以将 .deb 包重新打包成 .rpm,也可以直接从源文件打包成 .rpm。 安装 fpm sudo apt-get install ruby-dev sudo gem in…...

基于MATLAB典型去雾算法代码

1.3.1 Rentinex理论 Retinex(视网膜“Retina”和大脑皮层“Cortex”的缩写)理论是一种建立在科学实验和科学分析基础上的基于人类视觉系统(Human Visual System)的图像增强理论。该算法的基本原理模型最早是由Edwin Land&#xf…...

FrankenPHP实践

目录 1. 说明 2. 程序修改 3. 性能测试 4. 配置 4.1 Docker化部署 4.2 泛域名和证书设置 4.3 相关命令 5. 要点: 6. 参考 1. 说明 Frankenphp是一个先进的,结合了高性能Caddy服务器的PHP环境框架,它允许用户只需要少量改动&#xff…...

嵌入式硬件电子电路设计(一)开关电源Buck电路

目录 Buck电路基本结构 1. 开关闭合(SW 闭合) 2. 开关断开(SW 断开) 3. 开关控制和占空比 MP1584电路分析 其他Buck芯片的电路参考 Buck电路基本结构 下图是简化之后的BUCK电路主回路。下面分析输出电压的产生K闭合后&…...

java项目之协力服装厂服装生产管理系统的设计与实现(springboot)

风定落花生,歌声逐流水,大家好我是风歌,混迹在java圈的辛苦码农。今天要和大家聊的是一款基于springboot的协力服装厂服装生产管理系统的设计与实现。项目源码以及部署相关请联系风歌,文末附上联系信息 。 项目简介: …...

Java虚拟机的历程(jvm01)

Java虚拟机的历程(jvm01) Java虚拟机(JVM)作为Java语言的核心技术之一,自诞生以来经历了多次迭代与演变。不同的虚拟机在性能、功能以及适用场景上各有侧重。本文将介绍Java虚拟机发展历程中的一些重要虚拟机&#xf…...

[代码随想录Day4打卡] 24. 两两交换链表中的节点 19.删除链表的倒数第N个节点 面试题 02.07. 链表相交 142.环形链表II 总结

24. 两两交换链表中的节点 题目: 给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。 你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。 重点: 明确具体交换怎么做。交换其中1,2…...

java项目之校园周边美食探索及分享平台(springboot)

风定落花生,歌声逐流水,大家好我是风歌,混迹在java圈的辛苦码农。今天要和大家聊的是一款基于springboot的校园周边美食探索及分享平台。项目源码以及部署相关请联系风歌,文末附上联系信息 。 项目简介: 校园周边美食…...

支持 Mermaid 语言预览,用通义灵码画流程图

想像看图片一样快速读复杂代码和架构?通义灵码上新功能:智能问答支持 Mermaid 语言的预览模式,即支持代码逻辑可视化,可以把每段代码画成流程图,像脑图工具一样画出代码逻辑和框架。 操作步骤:选中代码块&a…...

cangjie仓颉程序设计-数据结构(四)

文章目录 ArrayListLinkedListHashSetHashMapTreeMap 本专栏还在持续更新: Cangjie仓颉程序设计-个人总结 这是双子专栏: 仓颉编程cangjie刷题录 这些数据结构都在std.collection.*中。暂时官方包还没有stack, queue等数据结构。服了 import std.coll…...

Redis中储存含LocalDateTime属性对象的序列化实现

目录 1.问题1 向Redis中存入序列化对象 1.1引入 : 1.2解决方案: 1.2.1首先引入依赖 1.2.2然后在RedisConfig中进行配置 1.3 介绍下ObjectMapper 1.3.1 ObjectMapper 1.3.2 objectMapper.registerModule(new JavaTimeModule()); 1.3.3 GenericJackson2Js…...

蚁剑的介绍和使用

蚁剑介绍 蚁剑(AntSword)是一个开源的跨平台网站管理工具,主要用于渗透测试和安全研究。它提供了一个图形化界面,方便用户管理和操作被攻陷的网站。 安装教程: github官网:https://github.com/AntSwordPro…...

C++之多态的深度剖析(2)

前言 在前面内容中,我们对多态进行了基本的了解,对其中的虚函数进行着重的介绍,本节内容我们将进一步对多态的底层进行观察了解看看它是如何实现的。 多态如何实现 从底层的角度Func函数中ptr->BuyTicket(),是如何作为ptr指向P…...

一篇文章 介绍 shiro反序列化漏洞

shiro反序列化漏洞 Shiro-550反序列化漏洞(CVE-2016-4437) 漏洞简介 shiro-550主要是由shiro的RememberMe内容反序列化导致的命令执行漏洞,造成的原因是默认加密密钥是硬编码在shiro源码中,任何有权访问源代码的人都可以知道默认加…...

pyav保存视频

目录 imageio替代pyav imageio替代pyav import imageio import numpy as np import torch# 创建一个随机的图像张量,形状为 (N, C, H, W) # 这里 N 30(帧数),C 3(通道数),H 64(…...

.bixi勒索病毒来袭:如何防止文件加密与数据丢失?

导言 在网络威胁剧烈的今天,勒索病毒已成为企业和个人面临的重大安全挑战,其中虫洞勒索病毒习得高强度的加密手段和急剧传播的特性引起关注。一旦感染,就会加密关键数据并索要赎金,导致数据无法访问并带来巨大的财务损失。更为严…...

浅谈 React Hooks

React Hooks 是 React 16.8 引入的一组 API,用于在函数组件中使用 state 和其他 React 特性(例如生命周期方法、context 等)。Hooks 通过简洁的函数接口,解决了状态与 UI 的高度解耦,通过函数式编程范式实现更灵活 Rea…...

可靠性+灵活性:电力载波技术在楼宇自控中的核心价值

可靠性灵活性:电力载波技术在楼宇自控中的核心价值 在智能楼宇的自动化控制中,电力载波技术(PLC)凭借其独特的优势,正成为构建高效、稳定、灵活系统的核心解决方案。它利用现有电力线路传输数据,无需额外布…...

Python ROS2【机器人中间件框架】 简介

销量过万TEEIS德国护膝夏天用薄款 优惠券冠生园 百花蜂蜜428g 挤压瓶纯蜂蜜巨奇严选 鞋子除臭剂360ml 多芬身体磨砂膏280g健70%-75%酒精消毒棉片湿巾1418cm 80片/袋3袋大包清洁食品用消毒 优惠券AIMORNY52朵红玫瑰永生香皂花同城配送非鲜花七夕情人节生日礼物送女友 热卖妙洁棉…...

嵌入式学习笔记DAY33(网络编程——TCP)

一、网络架构 C/S (client/server 客户端/服务器):由客户端和服务器端两个部分组成。客户端通常是用户使用的应用程序,负责提供用户界面和交互逻辑 ,接收用户输入,向服务器发送请求,并展示服务…...

基于Java+MySQL实现(GUI)客户管理系统

客户资料管理系统的设计与实现 第一章 需求分析 1.1 需求总体介绍 本项目为了方便维护客户信息为了方便维护客户信息,对客户进行统一管理,可以把所有客户信息录入系统,进行维护和统计功能。可通过文件的方式保存相关录入数据,对…...

Go 并发编程基础:通道(Channel)的使用

在 Go 中,Channel 是 Goroutine 之间通信的核心机制。它提供了一个线程安全的通信方式,用于在多个 Goroutine 之间传递数据,从而实现高效的并发编程。 本章将介绍 Channel 的基本概念、用法、缓冲、关闭机制以及 select 的使用。 一、Channel…...

【C++特殊工具与技术】优化内存分配(一):C++中的内存分配

目录 一、C 内存的基本概念​ 1.1 内存的物理与逻辑结构​ 1.2 C 程序的内存区域划分​ 二、栈内存分配​ 2.1 栈内存的特点​ 2.2 栈内存分配示例​ 三、堆内存分配​ 3.1 new和delete操作符​ 4.2 内存泄漏与悬空指针问题​ 4.3 new和delete的重载​ 四、智能指针…...

Linux nano命令的基本使用

参考资料 GNU nanoを使いこなすnano基础 目录 一. 简介二. 文件打开2.1 普通方式打开文件2.2 只读方式打开文件 三. 文件查看3.1 打开文件时,显示行号3.2 翻页查看 四. 文件编辑4.1 Ctrl K 复制 和 Ctrl U 粘贴4.2 Alt/Esc U 撤回 五. 文件保存与退出5.1 Ctrl …...

4. TypeScript 类型推断与类型组合

一、类型推断 (一) 什么是类型推断 TypeScript 的类型推断会根据变量、函数返回值、对象和数组的赋值和使用方式,自动确定它们的类型。 这一特性减少了显式类型注解的需要,在保持类型安全的同时简化了代码。通过分析上下文和初始值,TypeSc…...

【UE5 C++】通过文件对话框获取选择文件的路径

目录 效果 步骤 源码 效果 步骤 1. 在“xxx.Build.cs”中添加需要使用的模块 ,这里主要使用“DesktopPlatform”模块 2. 添加后闭UE编辑器,右键点击 .uproject 文件,选择 "Generate Visual Studio project files",重…...