代码随想录算法训练营(JAVA)| 第六章 二叉树 part06

2024-03-12 05:20

本文主要是介绍代码随想录算法训练营(JAVA)| 第六章 二叉树 part06,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

      今日任务 

力扣 654. 最大二叉树, 617. 合并二叉树,700. 二叉搜索树中的搜索,98. 验证二叉搜索树

题目 :654. 最大二叉树

思路

使用递归地方法遍历,每次找到当前数组中的最大值。很像 前序遍历

递归三部曲

①确定递归函数的参数和返回值

参数传入的是存放元素的数组,返回该数组构造的二叉树的头结点,返回类型是指向节点的指针。

②确定终止条件

题目中说了输入的数组大小一定是大于等于1的,所以我们不用考虑小于1的情况,那么当递归遍历的时候,如果传入的数组大小为1,说明遍历到了叶子节点了。

那么应该定义一个新的节点,并把这个数组的数值赋给新的节点,然后返回这个节点。 这表示一个数组大小是1的时候,构造了一个新的节点,并返回。

③确定单层递归的逻辑

1)先要找到数组中最大的值和对应的下标, 最大的值构造根节点,下标用来下一步分割数组。

2)最大值所在的下标左区间 构造左子树

        这里要判断maxValueIndex > 0,因为要保证左区间至少有一个数值。

3)最大值所在的下标右区间 构造右子树

        判断maxValueIndex < (nums.size() - 1),确保右区间至少有一个数值。

题解

class Solution {public TreeNode constructMaximumBinaryTree(int[] nums) {return func(nums, 0, nums.length);}public TreeNode func(int[] nums, int start, int end) {if (start == end) return null;int maxIndex = start;int maxValue = nums[start];for (int i = start + 1; i < end; i++ ) {if (nums[i] > maxValue) {maxValue = nums[i];maxIndex = i;}}TreeNode node = new TreeNode(maxValue);node.left = func(nums, start, maxIndex);node.right = func(nums, maxIndex + 1, end);return node;}
}

题目 :617. 合并二叉树

思路

  有合并链表那题的味了,只不过这里是累加

二叉树使用递归,本题使用哪种遍历都是可以的!

递归三部曲

①确定递归函数的参数和返回值:

首先要合入两个二叉树,那么参数至少是要传入两个二叉树的根节点,返回值就是合并之后二叉树的根节点。

②确定终止条件:

因为是传入了两个树,那么就有两个树遍历的节点t1 和 t2,如果t1 == NULL 了,两个树合并就应该是 t2 了(如果t2也为NULL也无所谓,合并之后就是NULL)。

反过来如果t2 == NULL,那么两个数合并就是t1(如果t1也为NULL也无所谓,合并之后就是NULL)。

③确定单层递归的逻辑:

单层递归的逻辑就比较好写了,这里我们重复利用一下t1这个树,t1就是合并之后树的根节点(就是修改了原来树的结构)。

那么单层递归中,就要把两棵树的元素加到一起。

题解

class Solution {public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {if (root1 == null) return root2;if (root2 == null) return root1;root1.val += root2.val;root1.left = mergeTrees(root1.left, root2.left);root1.right = mergeTrees(root1.right, root2.right);return root1;}
}

题目 :700. 二叉搜索树中的搜索

思路

注意:是 二叉搜索树,当前节点不空,然后将数值和左右子树的值进行比较。最坏情况是走到最后

递归三步曲

①确定递归函数的参数和返回值

递归函数的参数传入的就是根节点和要搜索的数值,返回的就是以这个搜索数值所在的节点。

②确定终止条件

如果root为空,或者找到这个数值了,就返回root节点。

③确定单层递归的逻辑

看看二叉搜索树的单层递归逻辑有何不同。

因为二叉搜索树的节点是有序的,所以可以有方向的去搜索。

如果root->val > val,搜索左子树,如果root->val < val,就搜索右子树,最后如果都没有搜索到,就返回NULL。

题解

class Solution {public TreeNode searchBST(TreeNode root, int val) {while (root != null) {if (root.val < val) {root = root.right;} else if (root.val > val) {root = root.left;} else {return root;}}return null;}
}

题目 :98. 验证二叉搜索树

思路

无论是递归还是迭代法,核心思想就是中序遍历(利用二叉搜索树的性质)

要知道中序遍历下,输出的二叉搜索树节点的数值是有序序列。

有了这个特性,验证二叉搜索树,就相当于变成了判断一个序列是不是递增的了。

迭代法中,定义一个pre判断当前节点值是否大于前一个结点值

题解 

递归
class Solution {TreeNode max;public boolean isValidBST(TreeNode root) {if (root == null) return true;boolean left = isValidBST(root.left);if (!left) return false;if (max != null && max.val >= root.val) return false;max = root;return isValidBST(root.right);}
}
迭代法
class Solution {public boolean isValidBST(TreeNode root) {if (root == null)return true;Stack<TreeNode> stack = new Stack<>();TreeNode pre = null;while (root != null || !stack.isEmpty()) {while (root != null) {stack.push(root);root = root.left;}TreeNode pop = stack.pop();if (pre != null && pre.val >= pop.val) {return false;}pre = pop;root = pop.right;}return true;}
}

这篇关于代码随想录算法训练营(JAVA)| 第六章 二叉树 part06的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/800252

相关文章

Java设计模式---迭代器模式(Iterator)解读

《Java设计模式---迭代器模式(Iterator)解读》:本文主要介绍Java设计模式---迭代器模式(Iterator),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,... 目录1、迭代器(Iterator)1.1、结构1.2、常用方法1.3、本质1、解耦集合与遍历逻辑2、统一

Java内存分配与JVM参数详解(推荐)

《Java内存分配与JVM参数详解(推荐)》本文详解JVM内存结构与参数调整,涵盖堆分代、元空间、GC选择及优化策略,帮助开发者提升性能、避免内存泄漏,本文给大家介绍Java内存分配与JVM参数详解,... 目录引言JVM内存结构JVM参数概述堆内存分配年轻代与老年代调整堆内存大小调整年轻代与老年代比例元空

深度解析Java DTO(最新推荐)

《深度解析JavaDTO(最新推荐)》DTO(DataTransferObject)是一种用于在不同层(如Controller层、Service层)之间传输数据的对象设计模式,其核心目的是封装数据,... 目录一、什么是DTO?DTO的核心特点:二、为什么需要DTO?(对比Entity)三、实际应用场景解析

Java 线程安全与 volatile与单例模式问题及解决方案

《Java线程安全与volatile与单例模式问题及解决方案》文章主要讲解线程安全问题的五个成因(调度随机、变量修改、非原子操作、内存可见性、指令重排序)及解决方案,强调使用volatile关键字... 目录什么是线程安全线程安全问题的产生与解决方案线程的调度是随机的多个线程对同一个变量进行修改线程的修改操

从原理到实战深入理解Java 断言assert

《从原理到实战深入理解Java断言assert》本文深入解析Java断言机制,涵盖语法、工作原理、启用方式及与异常的区别,推荐用于开发阶段的条件检查与状态验证,并强调生产环境应使用参数验证工具类替代... 目录深入理解 Java 断言(assert):从原理到实战引言:为什么需要断言?一、断言基础1.1 语

深度解析Java项目中包和包之间的联系

《深度解析Java项目中包和包之间的联系》文章浏览阅读850次,点赞13次,收藏8次。本文详细介绍了Java分层架构中的几个关键包:DTO、Controller、Service和Mapper。_jav... 目录前言一、各大包1.DTO1.1、DTO的核心用途1.2. DTO与实体类(Entity)的区别1

Java中的雪花算法Snowflake解析与实践技巧

《Java中的雪花算法Snowflake解析与实践技巧》本文解析了雪花算法的原理、Java实现及生产实践,涵盖ID结构、位运算技巧、时钟回拨处理、WorkerId分配等关键点,并探讨了百度UidGen... 目录一、雪花算法核心原理1.1 算法起源1.2 ID结构详解1.3 核心特性二、Java实现解析2.

SpringBoot整合liteflow的详细过程

《SpringBoot整合liteflow的详细过程》:本文主要介绍SpringBoot整合liteflow的详细过程,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋...  liteflow 是什么? 能做什么?总之一句话:能帮你规范写代码逻辑 ,编排并解耦业务逻辑,代码

JavaSE正则表达式用法总结大全

《JavaSE正则表达式用法总结大全》正则表达式就是由一些特定的字符组成,代表的是一个规则,:本文主要介绍JavaSE正则表达式用法的相关资料,文中通过代码介绍的非常详细,需要的朋友可以参考下... 目录常用的正则表达式匹配符正则表China编程达式常用的类Pattern类Matcher类PatternSynta

Spring Security中用户名和密码的验证完整流程

《SpringSecurity中用户名和密码的验证完整流程》本文给大家介绍SpringSecurity中用户名和密码的验证完整流程,本文结合实例代码给大家介绍的非常详细,对大家的学习或工作具有一定... 首先创建了一个UsernamePasswordAuthenticationTChina编程oken对象,这是S