「优选算法刷题」:计算布尔二叉树的值

一、题目

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

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

计算 一个节点的值方式如下:

  • 如果节点是个叶子节点,那么节点的  为它本身,即 True 或者 False 。
  • 否则,计算 两个孩子的节点值,然后将该节点的运算符对两个孩子值进行 运算 。

返回根节点 root 的布尔运算值。

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

叶子节点 是没有孩子的节点。

示例 1:

输入:root = [2,1,3,null,null,0,1]
输出:true
解释:上图展示了计算过程。
AND 与运算节点的值为 False AND True = False 。
OR 运算节点的值为 True OR False = True 。
根节点的值为 True ,所以我们返回 true 。

示例 2:

输入:root = [0]
输出:false
解释:根节点是叶子节点,且值为 false,所以我们返回 false 。

提示:

  • 树中节点数目在 [1, 1000] 之间。
  • 0 <= Node.val <= 3
  • 每个节点的孩子数为 0 或 2 。
  • 叶子节点的值为 0 或 1 。
  • 非叶子节点的值为 2 或 3 

二、思路解析

二叉树,大部分都是用到递归来实现的,所以,这道题我们可以有意地往递归上靠。

而递归一大重点就是,我们要寻找 每次递归中的相同子问题

也就是计算所有子节点的值,而这则是通过子节点的值运算出的。

抽象一下递归函数流程就是:

1. 当前问题规模为 n=1 时,即叶子节点,直接返回当前节点值;
2. 递归求得左右子节点的值;
3. 通过判断当前节点的逻辑运算符,计算左右子节点值运算得出的结果;

具体运算结合题目的条件即可,下面是完整代码实现👇

三、完整代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean evaluateTree(TreeNode root) {
        if(root.left == null){
            return root.val == 0 ? false : true; 
        }

        boolean left = evaluateTree(root.left);
        boolean right = evaluateTree(root.right);
        return root.val == 2 ? left | right : left & right;
    }
}

以上就是本篇博客的全部内容啦,如有不足之处,还请各位指出,期待能和各位一起进步!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/371283.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

1.0 Hadoop 教程

Hadoop 是一个开源的分布式计算和存储框架&#xff0c;由 Apache 基金会开发和维护。 Hadoop 为庞大的计算机集群提供可靠的、可伸缩的应用层计算和存储支持&#xff0c;它允许使用简单的编程模型跨计算机群集分布式处理大型数据集&#xff0c;并且支持在单台计算机到几千台计…

HBase相关面试准备问题

为什么选择HBase 1、海量存储 Hbase适合存储PB级别的海量数据&#xff0c;在PB级别的数&#xff0c;能在几十到几百毫秒内返回数据。这与Hbase的极易扩展性息息相关。正是因为Hbase良好的扩展性&#xff0c;才为海量数据的存储提供了便利。 2、列式存储 这里的列式存储其实说的…

【Android】RxJava系列01-基本概述和基本用法

少年啊&#xff0c;要永远相信美好的事情即将发生 【Android】RxJava系列01-基本概述和基本用法 1.RxJava的概述2.RxJava的作用3.观察者和被观察者4.背压5.RxJava的基本用法步骤一&#xff0c;创建Observer&#xff08;观察者&#xff09;步骤二&#xff0c;创建Observable&…

LangChain 最近发布的一个重要功能:LangGraph

LangGraph 是 LangChain 最近发布的一个重要功能&#xff0c;LangChain 进入多代理框架领域。通过建立在LangChain 之上&#xff0c;LangGraph 使开发人员可以轻松创建强大的代理运行时。 LangChain 使用其表达语言&#xff08;LCEL&#xff09;为开发人员构建定制链提供技术支…

深度学习(7)---Diffusion Model概念讲解

文章目录 一、基本概括1.1 概念讲解1.2 Denoise模块 二、Stable Diffusion2.1 概念讲解2.2 FID2.3 CLIP 一、基本概括 1.1 概念讲解 1. Diffusion Model是一种生成模型&#xff0c;通过连续添加高斯噪声来破坏训练数据&#xff0c;然后学习反转的去噪过程来恢复数据。它分为正…

go消息队列RabbitMQ - 订阅模式-fanout

1、发布订阅 订阅模式&#xff0c;消息被路由投递给多个队列&#xff0c;一个消息被多个消费者获取。 1&#xff09; 可以有多个消费者 2&#xff09; 每个消费者有自己的queue&#xff08;队列&#xff09; 3&#xff09; 每个队列都要绑定到Exchange&#xff08;交换机&…

【npm】安装全局包,使用时提示:不是内部或外部命令,也不是可运行的程序或批处理文件

问题 如图&#xff0c;明明安装Vue是全局包&#xff0c;但是使用时却提示&#xff1a; 解决办法 使用以下命令任意一种命令查看全局包的配置路径 npm root -g 然后将此路径添加到环境变量中去&#xff0c;这里注意&#xff0c;原本NodeJS的安装路径配置的环境变量不要删除&…

Sklearn、TensorFlow 与 Keras 机器学习实用指南第三版(一)

原文&#xff1a;Hands-On Machine Learning with Scikit-Learn, Keras, and TensorFlow 译者&#xff1a;飞龙 协议&#xff1a;CC BY-NC-SA 4.0 前言 机器学习海啸 2006 年&#xff0c;Geoffrey Hinton 等人发表了一篇论文&#xff0c;展示了如何训练一个能够以最先进的精度…

Tomcat组件架构与数据流

一、背景与简介 Tomcat我们都知道是一个开源的、实现了大部分Java EE、Servlet、JSP规范的Servlet容器, 允许我们将实现了Serlvet接口的Web程序war包进行部署运行。 但是你有对Tomcat做过细致的学习么? 我相信大部分同学和我一样&#xff0c;之前也是只会进行简单使用&#x…

IDEA插件ChatGPT - Easycode安装使用

IDEA插件ChatGPT - Easycode简介 ChatGPT - Easycode 是一个由 OpenAI 开发的 IntelliJ IDEA 插件&#xff0c;它可以利用 ChatGPT 的强大语言生成能力&#xff0c;帮助开发人员提高编码效率。 主要功能&#xff1a; 代码生成&#xff1a;可以根据自然语言描述生成代码&…

sqli-labs-master靶场训练笔记(21-38|精英级)

2024.1.30 level-21 (cookie 注入数据加密) 从页面上就可以看出这次的数据被 baes64 加密了 中国有句古话&#xff1a;师夷长技以制夷 &#xff0c;用base64加密后的数据即可爆出数据 加密前&#xff1a; admin and updatexml(1,concat(~,(select database()),~),1) and …

ReactNative实现宽度变化实现的动画效果

效果如上图所示&#xff0c;通过修改设备宽度实现动画效果 import React, {useRef, useEffect, useState} from react; import {Animated, Text, View, Image} from react-native;const FadeInView props > {const fadeAnim useRef(new Animated.Value(0)).current;React…

item_get_video-获取视频详情(bili.item_get_video)

B站&#xff08;Bilibili&#xff09;的item_get_video API用于获取视频的详细信息。通过调用该API&#xff0c;您将能够获得视频的基本信息、元数据、播放链接等。这使得开发者可以轻松地将B站视频集成到自己的应用程序或网站中&#xff0c;为用户提供更丰富的内容和更好的体验…

vue项目集成booststrap

1.首先安装bootstrap npm install bootstrap 我安装的是4.3的版本 2.在main.js中引用bootstrap import bootstrap/dist/css/bootstrap.css import bootstrap/dist/css/bootstrap.min.css import bootstrap/dist/js/bootstrap.js import bootstrap/dist/js/bootstrap.min.…

新数据不影响原来的数据

问题描述 新数据修改时&#xff0c;原来的数据也会受影响 const obj1 ref({ name: slx, age: 20 })const obj2 obj1obj2.value.name hhhhconsole.log(obj1, obj1.value)console.log(obj2, obj2.value)解决方法 (仅适用于对象 在这段代码中&#xff0c;obj1 和 obj2 指向同…

ASP.NET Core 预防开放式重定向攻击

写在前面 为预防钓鱼网站的常用套路&#xff0c;在进行 Web 应用程序的开发时&#xff0c;原则上应该将所有由用户提交的数据视为不可信。如果应用程序中包含了基于 URL 内容重定向的功能&#xff0c;需要确保这种类型的重定向操作只能在应用本地完成&#xff0c;或者明确判断…

MQTT在linux下服务端和客户端的应用

MQTT&#xff08;Message Queuing Telemetry Transport&#xff09;是一种轻量级、开放标准的消息传输协议&#xff0c;设计用于受限设备和低带宽、不稳定网络的通信。 MQTT的一些关键特点和概念&#xff1a; 发布/订阅模型&#xff1a; MQTT采用发布/订阅&#xff08;Publ…

编译原理本科课程 专题5 基于 SLR(1)分析的语义分析及中间代码生成程序设计

一、程序功能描述 本程序由C/C编写&#xff0c;实现了赋值语句语法制导生成四元式&#xff0c;并完成了语法分析和语义分析过程。 以专题 1 词法分析程序的输出为语法分析的输入&#xff0c;完成以下描述赋值语句 SLR(1)文法的语义分析及中间代码四元式的过程&#xff0c;实现…

基于tomcat的https(ssl)双向认证

一、背景介绍 某个供应商服务需要部署到海外&#xff0c;如果海外多个地区需要部署多个服务&#xff0c;最好能实现统一登录&#xff0c;这样可以减轻用户的使用负担&#xff08;不用记录一堆密码&#xff09;。由于安全问题&#xff08;可能会泄露用户数据&#xff09;&#x…

【大厂AI课学习笔记】1.5 AI技术领域(1)计算机视觉

人工智能的三大基础应用领域是&#xff0c;自然语言处理&#xff0c;语音识别&#xff0c;计算机视觉。 计算机视觉&#xff1a;定义、关键技术、技术发展、应用场景与商业化成功 一、计算机视觉的定义 计算机视觉&#xff0c;作为一个跨学科的领域&#xff0c;旨在研究如何让…