当前位置： 首页 > article >正文

代码随想录刷题day17丨654.最大二叉树，617.合并二叉树，700.二叉搜索树中的搜索，98.验证二叉搜索树

article 2024/9/24 5:33:37

代码随想录刷题day17丨654.最大二叉树，617.合并二叉树，700.二叉搜索树中的搜索，98.验证二叉搜索树

1.题目

1.1最大二叉树

  • 题目链接：654. 最大二叉树 - 力扣（LeetCode）

    在这里插入图片描述

  • 视频讲解：又是构造二叉树，又有很多坑！| LeetCode：654.最大二叉树_哔哩哔哩_bilibili

  • 文档讲解：https://programmercarl.com/0654.%E6%9C%80%E5%A4%A7%E4%BA%8C%E5%8F%89%E6%A0%91.html

  • 解题思路：递归（前序遍历）

    • 构造树一般采用的是前序遍历，因为先构造中间节点，然后递归构造左子树和右子树。
    • 确定递归函数的参数和返回值
      • 参数传入的是存放元素的数组，返回该数组构造的二叉树的头结点，返回类型是指向节点的指针。
    • 确定终止条件
      • 题目中说了输入的数组大小一定是大于等于1的，所以我们不用考虑小于1的情况，那么当递归遍历的时候，如果传入的数组大小为1，说明遍历到了叶子节点了。
      • 那么应该定义一个新的节点，并把这个数组的数值赋给新的节点，然后返回这个节点。 这表示一个数组大小是1的时候，构造了一个新的节点，并返回。
    • 确定单层递归的逻辑
      • 先要找到数组中最大的值和对应的下标， 最大的值构造根节点，下标用来下一步分割数组。
      • 最大值所在的下标左区间 构造左子树（这里要判断maxValueIndex > 0，因为要保证左区间至少有一个数值。）
      • 最大值所在的下标右区间 构造右子树（判断maxValueIndex < (nums.size() - 1)，确保右区间至少有一个数值。）

  • 代码：

    /**
 * 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) {
        if(nums.length == 1){
            return new TreeNode(nums[0]);
        }

        int maxValue = 0;
        int maxValueIndex = 0;
        for(int i =0;i < nums.length;i++){
            if(nums[i] > maxValue){
                maxValue = nums[i];
                maxValueIndex = i;
            } 
        }
        TreeNode node = new TreeNode(maxValue);

        if(maxValueIndex > 0){
            int[] arrLeft = new int[maxValueIndex];
            for(int i = 0;i < maxValueIndex;i++){
                arrLeft[i] = nums[i];
            } 
            node.left = constructMaximumBinaryTree(arrLeft);
        }

        if(maxValueIndex < nums.length -1){
            int[] arrRight = new int[nums.length - maxValueIndex - 1];
            for(int i = maxValueIndex + 1;i < nums.length;i++){
                arrRight[i -maxValueIndex - 1] = nums[i];
            }
            node.right = constructMaximumBinaryTree(arrRight);
        }
        return node;
    }
}

  • 总结：

    • 构造二叉树都是 前序遍历

1.2合并二叉树

  • 题目链接：617. 合并二叉树 - 力扣（LeetCode）

    在这里插入图片描述

  • 视频讲解：一起操作两个二叉树？有点懵！| LeetCode：617.合并二叉树_哔哩哔哩_bilibili

  • 文档讲解：https://programmercarl.com/0617.%E5%90%88%E5%B9%B6%E4%BA%8C%E5%8F%89%E6%A0%91.html

  • 解题思路：递归（前序遍历）

    • 其实和遍历一个树逻辑是一样的，只不过传入两个树的节点，同时操作。
    • 确定递归函数的参数和返回值：
      • 首先要合入两个二叉树，那么参数至少是要传入两个二叉树的根节点，返回值就是合并之后二叉树的根节点。
    • 确定终止条件：
      • 因为是传入了两个树，那么就有两个树遍历的节点t1 和 t2，如果t1 == NULL 了，两个树合并就应该是 t2 了（如果t2也为NULL也无所谓，合并之后就是NULL）。
      • 反过来如果t2 == NULL，那么两个数合并就是t1（如果t1也为NULL也无所谓，合并之后就是NULL）。
    • 确定单层递归的逻辑：
      • 单层递归的逻辑就比较好写了，这里我们重复利用一下t1这个树，t1就是合并之后树的根节点（就是修改了原来树的结构）。

  • 代码：

    /**
 * 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 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;
    }
}

  • 总结：

    • 优先掌握递归
    • 本题递归用中序和后序也都可以，换个顺序就行，前序更方便直观理解

1.3二叉搜索树中的搜索

  • 题目链接：700. 二叉搜索树中的搜索 - 力扣（LeetCode）

    在这里插入图片描述

  • 视频讲解：不愧是搜索树，这次搜索有方向了！| LeetCode：700.二叉搜索树中的搜索_哔哩哔哩_bilibili

  • 文档讲解：https://programmercarl.com/0700.%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E4%B8%AD%E7%9A%84%E6%90%9C%E7%B4%A2.html

  • 解题思路：递归法或者迭代法

    • 确定递归函数的参数和返回值
      • 递归函数的参数传入的就是根节点和要搜索的数值，返回的就是以这个搜索数值所在的节点。
    • 确定终止条件
      • 如果root为空，或者找到这个数值了，就返回root节点。
    • 确定单层递归的逻辑
      • 因为二叉搜索树的节点是有序的，所以可以有方向的去搜索。
      • 如果root->val > val，搜索左子树，如果root->val < val，就搜索右子树，最后如果都没有搜索到，就返回NULL。

  • 代码：

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

    class Solution {
    // 迭代，普通二叉树
    public TreeNode searchBST(TreeNode root, int val) {
        if (root == null || root.val == val) {
            return root;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode pop = stack.pop();
            if (pop.val == val) {
                return pop;
            }
            if (pop.right != null) {
                stack.push(pop.right);
            }
            if (pop.left != null) {
                stack.push(pop.left);
            }
        }
        return null;
    }
}


class Solution {
    // 迭代，利用二叉搜索树特点，优化，可以不需要栈
    public TreeNode searchBST(TreeNode root, int val) {
        while (root != null)
            if (val < root.val) root = root.left;
            else if (val > root.val) root = root.right;
            else return root;
        return null;
    }
}

  • 总结：

    • 递归和迭代 都可以掌握一下，因为本题比较简单

1.4验证二叉搜索树

  • 题目链接：98. 验证二叉搜索树 - 力扣（LeetCode）

    在这里插入图片描述

  • 视频讲解：你对二叉搜索树了解的还不够！ | LeetCode：98.验证二叉搜索树_哔哩哔哩_bilibili

  • 文档讲解：https://programmercarl.com/0098.%E9%AA%8C%E8%AF%81%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91.html

  • 解题思路：递归（中序遍历）

    • 中序遍历看是否单调递增
    • 要知道中序遍历下，输出的二叉搜索树节点的数值是有序序列。有了这个特性，验证二叉搜索树，就相当于变成了判断一个序列是不是递增的了。
    • 用双指针思想优化递归过程做该题效果最好

  • 代码：

    /**
 * 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 {
    TreeNode pre = null; // 类的成员变量，用来保存中序遍历过程中前一个节点
    public boolean isValidBST(TreeNode root) {
        if(root == null){
            return true;// 空树是有效的二叉搜索树
        }
        boolean left = isValidBST(root.left);
        if(pre != null && pre.val >= root.val){
            return false;
        }
        pre = root;// 更新 pre 为当前节点
        boolean right = isValidBST(root.right);
        return left && right;// 返回左子树和右子树是否都是有效的 BST
    }
}

  • 总结：

    • 遇到 搜索树，一定想着中序遍历，这样才能利用上特性。
    • 但本题是有陷阱的
      • 不能单纯的比较左节点小于中间节点，右节点大于中间节点就完事了。
      • 我们要比较的是 左子树所有节点小于中间节点，右子树所有节点大于中间节点。

http://www.kler.cn/news/283841.html

相关文章：

  • Java线程生命周期详解_（1）
  • 在 Maven 的 POM 文件中配置 npm 镜像源
  • SpringMVC处理流程介绍
  • 【HuggingFace Transformers】BertSelfOutput 和 BertOutput源码解析
  • 开源个人云存储管理专家：Cloudreve
  • 零基础入门转录组数据分析——单基因ROC分析
  • Leetcode Java学习记录——动态规划基础_3
  • 尚硅谷大数据技术-Kafka视频教程-笔记01【Kafka 入门】
  • 8月30复盘日记
  • k8s-pod 实战四 什么是 Kubernetes Pod？如何在生产环境中使用它？（学习专场，实战就看这一篇就够了）
  • 把http网站变成https
  • WPF 使用PdfiumViewer实现PDF预览与打印
  • RabbitMQ本地Ubuntu系统环境部署与无公网IP远程连接服务端实战演示
  • element input限制输入框只能输入数字
  • 深入解析：文本分析模型性能评估的艺术与科学
  • 浅谈对分布式锁的认识
  • React中实现antd自定义图标，鼠标悬浮变色
  • Java算法之BogoSort（或称为Permutation Sort、Monkey Sort）
  • day39(了解docker-compose,docker-compose编排容器，配置harbor服务)
  • PneumoLLM: 利用大语言模型的力量进行尘肺病诊断| 文献速递-大模型与多模态诊断阿尔茨海默症与帕金森疾病应用
  • 数据的时光机：SQL中实现数据版本控制的策略
  • Go微服务开发框架DMicro的设计思路
  • Scala之高阶面向对象编程
  • 【NCom】:通用负压退火方法构建超高负载单原子催化剂库
  • Python 3.11 从入门到实战1（环境准备）
  • 鸿蒙XComponent组件的认识
  • FastJson序列化驼峰-下划线转换问题踩坑记录
  • 基于Spring Boot的文字识别系统
  • 逆波兰表达式求值
  • 【面试经验】华为产品行销经理面经