二叉树(属性、修改与构造)

226. 翻转二叉树

题目

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

示例 1：

在这里插入图片描述

输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]

答案

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root==null){
            return root;
        }
        Queue<TreeNode> queue = new LinkedList();
        queue.offer(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            for(int i=0;i<size;i++){
                TreeNode curr = queue.poll();
                swap(curr);//只能传 curr 值传递
                if(curr.left!=null) queue.offer(curr.left);
                if(curr.right!=null) queue.offer(curr.right);
            }
        }
        return root;
    }
    void swap(TreeNode root){
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
    }
}








101. 对称二叉树

题目

给你一个二叉树的根节点 root ， 检查它是否轴对称。

示例 1：

在这里插入图片描述

输入：root = [1,2,2,3,4,4,3]
输出：true

答案

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root==null){
            return true;
        }
        Queue<TreeNode> queue = new LinkedList();
        queue.offer(root.left);
        queue.offer(root.right);
        while(!queue.isEmpty()){
            int size = queue.size();
            for(int i=0;i<size;i++){
                TreeNode left = queue.poll();
                TreeNode right = queue.poll();
                if(left==null && right==null){
                    continue;
                }
                if(left==null || right==null || left.val!=right.val){
                    return false;
                }
                queue.offer(left.left);//null 也放进去
                queue.offer(right.right);
                queue.offer(left.right);
                queue.offer(right.left);
            }
        }
        return true;
    }
}







104. 二叉树的最大深度

题目

给定一个二叉树 root ，返回其最大深度。

二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

示例 1：

在这里插入图片描述

输入：root = [3,9,20,null,null,15,7]
输出：3

答案

class Solution {
    public int maxDepth(TreeNode root) {
        int res = 0;
        if(root==null){
            return res;
        }
        Queue<TreeNode> queue = new LinkedList();
        queue.offer(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            res++;
            for(int i=0;i<size;i++){
                TreeNode curr = queue.poll();
                if(curr.left!=null) queue.offer(curr.left);
                if(curr.right!=null) queue.offer(curr.right);
            }
        }
        return res;
    }
}






111. 二叉树的最小深度

题目

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

**说明：**叶子节点是指没有子节点的节点。

示例 1：

在这里插入图片描述

输入：root = [3,9,20,null,null,15,7]
输出：2

答案

class Solution {
    public int minDepth(TreeNode root) {
        int res = 0;
        if(root==null){
            return res;
        }
        Queue<TreeNode> queue = new LinkedList();
        queue.offer(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            res++;
            for(int i=0;i<size;i++){
                TreeNode curr = queue.poll();
                if(curr.left==null && curr.right==null){
                    return res;
                }
                if(curr.left!=null) queue.offer(curr.left);
                if(curr.right!=null) queue.offer(curr.right);
            }
        }
        return res;
    }
}







222. 完全二叉树的节点个数

题目

给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。

完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。

示例 1：

在这里插入图片描述

输入：root = [1,2,3,4,5,6]
输出：6

答案

class Solution {
    public int countNodes(TreeNode root) {
        int res = 0;
        if(root==null){
            return res;
        }
        Queue<TreeNode> queue = new LinkedList();
        queue.offer(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            for(int i=0;i<size;i++){
                TreeNode curr = queue.poll();
                res++;
                if(curr.left!=null) queue.offer(curr.left);
                if(curr.right!=null) queue.offer(curr.right);
            }
        }
        return res;
    }
}







110. 平衡二叉树

题目

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

示例 1：

在这里插入图片描述

输入：root = [3,9,20,null,null,15,7]
输出：true

答案

class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root==null){
            return true;
        }
        return Math.abs(deal(root.left)-deal(root.right))<2 //根 左 右
                && isBalanced(root.left) 
                && isBalanced(root.right);
    }
    int deal(TreeNode root){
        if(root==null){
            return 0;
        }
        return Math.max(deal(root.left),deal(root.right)) + 1;
    }
}







257. 二叉树的所有路径

题目

给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。

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

示例 1：

在这里插入图片描述

输入：root = [1,2,3,null,5]
输出：["1->2->5","1->3"]

答案

class Solution {
    List<String> res = new ArrayList();
    public List<String> binaryTreePaths(TreeNode root) {
        if(root==null){
            return res;
        }
        deal(root,"");
        return res;
    }
    void deal(TreeNode root,String str){
        if(root==null){
            return;
        }
        if(root.left==null && root.right==null){
            res.add(new StringBuilder(str).append(root.val+"").toString());
            return;
        }
        str = new StringBuilder(str).append(root.val+"").append("->").toString();//根 左 右
        deal(root.left,str);
        deal(root.right,str);
    }
}








404. 左叶子之和

题目

给定二叉树的根节点 root ，返回所有左叶子之和。

示例 1：

在这里插入图片描述

输入: root = [3,9,20,null,null,15,7] 
输出: 24 
解释: 在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24

答案

class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        int res = 0;
        if(root==null){
            return res;
        }
        Queue<TreeNode> queue = new LinkedList();
        queue.offer(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            for(int i=0;i<size;i++){
                TreeNode curr = queue.poll();
                if(curr.left!=null){
                    queue.offer(curr.left);
                    if(curr.left.left==null && curr.left.right==null){//判断是左叶子节点
                        res += curr.left.val;
                    }
                }
                if(curr.right!=null) queue.offer(curr.right);
            }
        }
        return res;
    }
}








513. 找树左下角的值

题目

给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。

假设二叉树中至少有一个节点。

示例 1:

在这里插入图片描述

输入: root = [2,1,3]
输出: 1

答案

class Solution {
    public int findBottomLeftValue(TreeNode root) {
        int res = 0;
        Queue<TreeNode> queue = new LinkedList();
        queue.offer(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            for(int i=0;i<size;i++){
                TreeNode curr = queue.poll();
                if(i==0){
                    res =curr.val;
                }
                if(curr.left!=null) queue.offer(curr.left);
                if(curr.right!=null) queue.offer(curr.right);
            }
        }
        return res;
    }
}








112. 路径总和

题目

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

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

示例 1：

在这里插入图片描述

输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true
解释：等于目标和的根节点到叶节点路径如上图所示。

答案

class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if(root==null){
            return false;
        }
        if(root.left==null && root.right==null){//根 左 右
            return targetSum==root.val;
        }
        return hasPathSum(root.left,targetSum-root.val) || hasPathSum(root.right,targetSum-root.val);
    }
}








105. 从前序与中序遍历序列构造二叉树

题目

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

示例 1:

在这里插入图片描述

输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]

答案

class Solution {
    Map<Integer,Integer> map = new HashMap();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        for(int i=0;i<inorder.length;i++){
            map.put(inorder[i],i);
        }
        TreeNode res = deal(preorder,0,preorder.length,inorder,0,inorder.length);
        return res;
    }
    TreeNode deal(int[] preorder,int preBegin,int preEnd,int[] inorder,int inBegin,int inEnd){
        if(preBegin>=preEnd || inBegin>=inEnd){
            return null;
        }
        int currIndex = map.get(preorder[preBegin]);//根左右
        int leftLen = currIndex - inBegin;
        TreeNode curr = new TreeNode(preorder[preBegin]);
        
        curr.left = deal(preorder,preBegin+1,preBegin+1+leftLen,inorder,inBegin,inBegin+leftLen);
        curr.right = deal(preorder,preBegin+1+leftLen,preEnd,inorder,currIndex+1,inEnd);
        return curr;
    }
}







106. 从中序与后序遍历序列构造二叉树

题目

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

示例 1:

在这里插入图片描述

输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出：[3,9,20,null,null,15,7]

答案

class Solution {
    Map<Integer,Integer> map = new HashMap();
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        for(int i=0;i<inorder.length;i++){
            map.put(inorder[i],i);
        }
        return deal(inorder,0,inorder.length,postorder,0,postorder.length);
    }
    TreeNode deal(int[] inorder,int inBegin,int inEnd,int[] postorder,int postBegin,int postEnd){
        if(inBegin>=inEnd || postBegin>=postEnd){
            return null;
        }
        int currIndex = map.get(postorder[postEnd-1]);
        int leftLen = currIndex - inBegin;
        TreeNode curr = new TreeNode(postorder[postEnd-1]);
        curr.left = deal(inorder,inBegin,currIndex,postorder,postBegin,postBegin+leftLen);
        curr.right = deal(inorder,currIndex+1,inEnd,postorder,postBegin+leftLen,postEnd-1);//postEnd-1根节点
        return curr;
    }
}








654. 最大二叉树

题目

给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:

  1. 创建一个根节点，其值为 nums 中的最大值。
  2. 递归地在最大值 左边 的 子数组前缀上 构建左子树。
  3. 递归地在最大值 右边 的 子数组后缀上 构建右子树。

返回 nums 构建的 *最大二叉树* 。

示例 1：

在这里插入图片描述

输入：nums = [3,2,1,6,0,5]
输出：[6,3,5,null,2,0,null,null,1]

答案

class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return deal(nums,0,nums.length);
    }
    TreeNode deal(int[] nums,int begin,int end){
        if(end-begin<1){
            return null;
        }
        if(end-begin==1){
            return new TreeNode(nums[begin]);
        }
		//找最大值的下标
        int maxIndex = begin;
        int maxIndexVal = nums[begin];
        for(int i=begin+1;i<end;i++){
            if(nums[i]>maxIndexVal){
                maxIndex = i;
                maxIndexVal = nums[i];
            }
        }
        
        TreeNode curr = new TreeNode(maxIndexVal);//根 左 右 构建树
        curr.left = deal(nums,begin,maxIndex);
        curr.right = deal(nums,maxIndex+1,end);
        return curr;
    }
}







617. 合并二叉树

题目

给你两棵二叉树： root1 和 root2 。

想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。

返回合并后的二叉树。

注意: 合并过程必须从两个树的根节点开始。

示例 1：

在这里插入图片描述

输入：root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
输出：[3,4,5,5,4,null,7]

答案

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

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

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

相关文章

python3安装chrome，chromedriver亲测有效

python3安装chrome，chromedriver亲测有效

客户用python写了个脚本&#xff0c;需要用到chrome和chromedriver扩展&#xff0c;结果说安装不了&#xff0c;各种报错&#xff0c;好吧我来研究一下。众所周知linux自带python2.7&#xff0c;根据报错查了一下资料发现是版本冲突导致的&#xff0c;系统自带2.7&#xff0c;代…
阅读更多...
针对ETC系统的OBE-SAM模块设计方案

针对ETC系统的OBE-SAM模块设计方案

ETC&#xff08;Electrical Toll Collection&#xff09;不停车收费是目前世界上最先进的路桥收费方式。通过安装在车辆挡风玻璃上的车载单元与安装在收费站 ETC 车道上的路侧单元之间的微波专用短程通讯&#xff0c;利用计算机联网技术与银行进行后台结算处理&#xff0c;从而…
阅读更多...
typescript 学习

typescript 学习

一.typescript是Javascript的超集，在javascript中添加特性的语言扩展，支持ES6标准。 二.typescript中新增了：类型批注和编译时类型检查，类型推断，类型擦除，接口，枚举，Mixin,泛型编程，名字空间，元组，await等 三.vscode 中怎样使用typescript 1. 安装VSCode （官网下…
阅读更多...
SSL 证书，了解一下常识

SSL 证书，了解一下常识

公司的网站、应用怎么才能保证在互联网上安全运行&#xff0c;不被攻击、盗取数据呢&#xff1f; 创业必经之路&#xff0c;一步一步走就对了&#xff0c;可能没赶上红利期&#xff0c;但不做就等于0。 概述 SSL 证书&#xff08;SSL Certificates&#xff09;又称数字证书&am…
阅读更多...
常见控件应用

常见控件应用

常见控件应用 1.操作Ajax选项2.滑动滑块操作 1.操作Ajax选项 Ajax即Asynchronous JavaScript and XML&#xff08;异步JavaScript和XML&#xff09;&#xff0c;是指一种创建交互式、快速动态网页应用的网页开发技术。通过在后台与服务器进行少量数据交换&#xff0c;Ajax可以…
阅读更多...
Python与FPGA——图像锐化

Python与FPGA——图像锐化

文章目录 前言一、图像锐化二、Python robert锐化三、Python sobel锐化四、Python laplacian锐化五、FPGA sobel锐化总结 前言 在增强图像之前一般会先对图像进行平滑处理以减少或消除噪声&#xff0c;图像的能量主要集中在低频部分&#xff0c;而噪声和图像边缘信息的能量主要…
阅读更多...
Spring Boot 生成与解析Jwt

Spring Boot 生成与解析Jwt

Spring Boot 生成与解析Jwt Maven依赖 <dependency><groupId>io.jsonwebtoken</groupId><artifactId>jjwt</artifactId><version>0.9.1</version> </dependency>生成&解析 package yang;import io.jsonwebtoken.Claims…
阅读更多...
DDS技术概述及测试策略与方案

DDS技术概述及测试策略与方案

随着车载通信技术的快速发展&#xff0c;传统的通信技术在满足车载通信需求方面面临着一些挑战。车载通信对实时性、可靠性以及通信带宽的需求越来越高&#xff0c;同时车载通信环境存在多路径衰落、信号干扰等问题&#xff0c;这些都给通信技术的选择和应用带来了一定的挑战。…
阅读更多...
沐风老师3DMAX快速布尔QuickBoolean插件安装和使用教程

沐风老师3DMAX快速布尔QuickBoolean插件安装和使用教程

3DMAX快速布尔QuickBoolean插件安装和使用教程 3DMAX快速布尔QuickBoolean插件是一组工具&#xff0c;用于对具有预设轮廓的当前选定对象快速执行ProBoolean运算&#xff0c;如并集、相交、空心、修剪、减法、拆分和刀。 它的工作原理与SketchUp的Solid Tools非常相似&#xf…
阅读更多...
qt如何配置ros环境

qt如何配置ros环境

在Qt5.7的版本可以使用bash -i -c来启动qt&#xff0c;让Qt自己识别系统环境&#xff0c;不知道为什么Qt在之后的版本&#xff0c;这样使用都失效了。因为它会默认把CMAKE_PREFIX_PATH修改掉。 网上还有安装ros插件版本的qt creator&#xff0c;感觉失去了一些灵活性。 自己测试…
阅读更多...
STM32CubeIDE基础学习-STM32CubeIDE软件配置下载器方法

STM32CubeIDE基础学习-STM32CubeIDE软件配置下载器方法

STM32CubeIDE基础学习-STM32CubeIDE软件配置下载器方法 文章目录 STM32CubeIDE基础学习-STM32CubeIDE软件配置下载器方法前言第1章 配置ST-LINK下载器第2章 配置DAP下载器总结 前言 这个软件编译完之后&#xff0c;可以使用下载器进行在线下载程序或仿真调试程序&#xff0c;也…
阅读更多...
高效办公-电脑软件安装简介

高效办公-电脑软件安装简介

之前大概了解了一下应用软件就是在操作系统上面安装的一些办公软件。今天来学习下怎么下载软件、怎么安装、怎样卸载&#xff1f; 一、软件类型 电脑操作系统上可以根据自己的需求按照许多软件实现办公、影音娱乐等功能&#xff0c;大概分类有下面的一些&#xff0c;但是只是一…
阅读更多...
设计模式(十)：抽象工厂模式（创建型模式）

设计模式(十)：抽象工厂模式（创建型模式）

Abstract Factory&#xff0c;抽象工厂&#xff1a;提供一个创建一系列相关或相互依赖对 象的接口&#xff0c;而无须指定它们的具体类。 之前写过简单工厂和工厂方法模式(创建型模式)&#xff0c;这两种模式比较简单。 简单工厂模式其实不符合开闭原则&#xff0c;即对修改关闭…
阅读更多...
Linux：kubernetes（k8s）允许在任意节点使用kubectl命令（5）

Linux：kubernetes（k8s）允许在任意节点使用kubectl命令（5）

我们部署好了主节点以后&#xff0c;我们使用kubectl命令 一切正常&#xff0c;而我们到了别的node上使用 就显示一个这个 这个原因是因为我们开始就配置了master的一个配置文件&#xff0c;在/root/.kube/config 里&#xff0c;而我们的从节点不知道去找那个api接口所以就报…
阅读更多...
一分钟安装使用教程，无需服务器，一台电脑就可使用！全网最快速便捷使用Claude 3方法！

一分钟安装使用教程，无需服务器，一台电脑就可使用！全网最快速便捷使用Claude 3方法！

随着AI的应用变广&#xff0c;各类AI程序已逐渐普及&#xff0c;尤其是在一些日常办公、学习等与撰写/翻译文稿密切相关的场景&#xff0c;大家都希望找到一个适合自己的稳定可靠的ChatGPT软件来使用。 ChatGPT-Next-Web就是一个很好的选择。它是一个Github上超人气的免费开源…
阅读更多...
【mogoose】对查询的数据进行过滤不需要展示的信息

【mogoose】对查询的数据进行过滤不需要展示的信息

数据库结构如下 我只要email userName sex role 几个数据&#xff0c;其余不要 {_id: new ObjectId(65e7b6df8d06a0623fa899f5),email: 12345qq.com,pwd: $2a$10$eLJ9skKEsQxvzHf5X8hbaOXKtg8GCHBeieieSN6Usu17D2DPaI44i,userName: 默认昵称0769,sex: 0,token: {upCount: 0,_…
阅读更多...
想交易盈利？Anzo Capital昂首资本发现了一本畅销书

想交易盈利？Anzo Capital昂首资本发现了一本畅销书

要想在复杂多变的外汇市场中迅速加深了解并想通过交易每天都可以盈利&#xff0c;是通过每天阅读大量的书籍吗&#xff1f;是每天成为行业培训网络资源和论坛的常客吗&#xff1f;是通过花钱请有经验的交易者进行个人培训吗&#xff1f;还是进行EA交易呢&#xff1f; 都不是&a…
阅读更多...
C# LINQ基础

C# LINQ基础

LINQ基础 1. 入门2. 运算符流语法2.1 连续使用查询运算符2.2 使用Lambda表达式2.2.1 Lambda表达式及Func的方法签名2.2.2 Lambda表达式和元素类型2.2.3 自然排序2.2.4 其他查询运算符 3 查询表达式4 延迟执行4.1 重复执行4.2 捕获的变量4.3 延迟加载的工作原理4.4 查询语句的执…
阅读更多...
如何将TIDB作为Mysql的从库实现实时数据同步

如何将TIDB作为Mysql的从库实现实时数据同步

------------------------------------------------------------------- 欢迎关注作者 墨天伦：潇湘秦的个人主页 - 墨天轮 CSDN：潇湘秦-CSDN博客 公众号：潇湘秦的DBA之路 ------------------------------------------------------------------- 近期一个MES项目架构比较复…
阅读更多...
Spark实战-基于Spark日志清洗与数据统计以及Zeppelin使用

Spark实战-基于Spark日志清洗与数据统计以及Zeppelin使用

Saprk-日志实战 一、用户行为日志 1.概念 用户每次访问网站时所有的行为日志(访问、浏览、搜索、点击)用户行为轨迹&#xff0c;流量日志2.原因 分析日志&#xff1a;网站页面访问量网站的粘性推荐3.生产渠道 (1)Nginx(2)Ajax4.日志内容 日志数据内容&#xff1a;1.访问的…
阅读更多...
最新文章

Copyright @ 2022~2023