代码随想录 Day20 - 二叉树(六)

简介: 代码随想录 Day20 - 二叉树(六)

654. 最大二叉树

/**
 * 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 TreeNode constructMaximumBinaryTree(int[] nums) {
        return buildMaxTreeFromArray(nums, 0, nums.length);
    }
    private TreeNode buildMaxTreeFromArray(int[] nums, int start, int end) {
        if (end - start < 1) {
            return null;
        }
        if (end - start < 2) {
            return new TreeNode(nums[start]);
        }
        int maxIndex = start;
        int maxNum = nums[start];
        for (int i = start; i < end; i++) {
            if (nums[i] > maxNum) {
                maxIndex = i;
                maxNum = nums[i];
            }
        }
        TreeNode root = new TreeNode(maxNum);
        root.left = buildMaxTreeFromArray(nums, start, maxIndex);
        root.right = buildMaxTreeFromArray(nums, maxIndex + 1, end);
        return root;
    }
}


617. 合并二叉树

package jjn.carl.binary_tree;
import commons.TreeNode;
/**
 * @author Jjn
 * @since 2023/7/18 00:10
 */
public class LeetCode617 {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if (root1 == null) {
            return root2;
        }
        if (root2 == null) {
            return root1;
        }
        TreeNode root = new TreeNode(root1.val + root2.val);
        root.left = mergeTrees(root1.left, root2.left);
        root.right = mergeTrees(root1.right, root2.right);
        return root;
    }
}


700. 二叉搜索树中的搜索

递归搜索,比较左子树与根节点,右子树与根节点。

/**
 * 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 TreeNode searchBST(TreeNode root, int val) {
        if(root == null) {
            return null;
        }
        if(root.val == val) {
            return root;
        }
        if(root.val < val) {
            return searchBST(root.right, val);
        }
        return searchBST(root.left, val);
    }
}


98. 验证二叉搜索树

不断比较左子树的节点值是否在区间,由于节点的值可能是 Integer.MIN_VALUE 或者 Integer.MAX_VALUE,因此需要用 Long 的最大与最小值来比较。

/**
 * 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 isValidBST(TreeNode root) {
        return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
    private boolean isValidBST(TreeNode node, long lower, long upper) {
        if (node == null) {
            return true;
        }
        if (node.val <= lower || node.val >= upper) {
            return false;
        }
        return isValidBST(node.left, lower, node.val) && isValidBST(node.right, node.val, upper);
    }
}

目录
相关文章
|
安全 Java API
解决 Swagger API 未授权访问漏洞:完善分析与解决方案
Swagger 是一个用于设计、构建、文档化和使用 RESTful 风格的 Web 服务的开源软件框架。它通过提供一个交互式文档页面,让开发者可以更方便地查看和测试 API 接口。然而,在一些情况下,未经授权的访问可能会导致安全漏洞。本文将介绍如何解决 Swagger API 未授权访问漏洞问题。
|
5月前
|
数据可视化 数据挖掘
Scanpy 分析 scRNA-seq:降维与聚类
Scanpy 分析 scRNA-seq:降维与聚类
Scanpy 分析 scRNA-seq:降维与聚类
|
10月前
|
消息中间件 存储 缓存
如果对方没做幂等!记一次生产订单重复的反思
公司旧系统中发现一个严重bug:用户支付一年服务费,系统却将有效期增加了两年。经分析,原因是消息队列(MQ)向第三方服务发送了两次消息,且该接口未实现幂等性控制。此问题可能导致财务损失和信誉受损。解决方案包括:生产者端通过请求频率限制、幂等键等防重措施;消费者端利用缓存和数据库确保幂等性;消息队列层配置去重功能、TTL和死信队列等。
102 0
|
缓存 JavaScript 前端开发
「offer来了」从基础到进阶原理,从vue2到vue3,48个知识点保姆级带你巩固vuejs知识体系
该文章全面覆盖了Vue.js从基础知识到进阶原理的48个核心知识点,包括Vue CLI项目结构、组件生命周期、响应式原理、Composition API的使用等内容,并针对Vue 2与Vue 3的不同特性进行了详细对比与讲解。
410 13
「offer来了」从基础到进阶原理,从vue2到vue3,48个知识点保姆级带你巩固vuejs知识体系
|
12月前
|
Rust 关系型数据库 Linux
Rainfrog: 轻量级数据库管理工具
【10月更文挑战第3天】
219 0
|
前端开发 JavaScript 数据管理
前端框架对比:React、Vue与Angular
【7月更文挑战第2天】React、Vue和Angular是前端三大框架,各有特色。React以组件化和虚拟DOM著称,适合大型SPA;Vue轻量且易用,适用于快速开发;Angular是全面解决方案,适合复杂应用,但学习成本高。选择取决于项目需求和团队技能。
|
11月前
|
存储 NoSQL 关系型数据库
Redis的ZSet底层数据结构,ZSet类型全面解析
Redis的ZSet底层数据结构,ZSet类型全面解析;应用场景、底层结构、常用命令;压缩列表ZipList、跳表SkipList;B+树与跳表对比,MySQL为什么使用B+树;ZSet为什么用跳表,而不是B+树、红黑树、二叉树
|
前端开发
CSS动画新潮流:炫酷水波效果,让网页元素生动起来!
CSS动画新潮流:炫酷水波效果,让网页元素生动起来!
|
存储 Java Serverless
ACK One Argo 工作流集群:玩转容器对象存储
ACK One Argo 工作流集群:玩转容器对象存储
ACK One Argo 工作流集群:玩转容器对象存储
|
供应链 物联网 新制造
云上智能制造:重塑工业未来,驱动智能升级的新篇章
云上智能制造平台作为智能制造领域的重要创新成果,正以其独特的优势和广泛的应用场景引领着制造业的智能化升级。未来,随着技术的不断进步和应用的不断拓展,云上智能制造平台将在推动产业升级、提升生产效率、优化资源配置等方面发挥更加重要的作用。我们有理由相信,在云上智能制造平台的助力下,制造业将迎来更加辉煌的未来。
805 0