程序员经验分享-hwhale

leetcode刷题（7）二叉树（1）

2023-11-19

哈喽大家好，这是我leetcode刷题的第七篇，这两天我将更新leetcode上关于二叉树方面的题目，如果大家对这方面感兴趣的话，欢迎大家持续关注，谢谢大家。
那么我们就进入今天的主题。

1.二叉树的前序遍历

leetcode之二叉树的前序遍历（难度：简单）

题目要求

给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

/**
 * 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 List<Integer> preorderTraversal(TreeNode root) {
}

示例

示例 1：
在这里插入图片描述

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

示例 2：
输入：root = []
输出：[]

示例 3：

输入：root = [1]
输出：[1]

示例 4：
在这里插入图片描述

输入：root = [1,2]
输出：[1,2]

示例 5：
在这里插入图片描述

输入：root = [1,null,2]
输出：[1,2]

做题思路

二叉树的遍历分为前序遍历、中序遍历和后序遍历，前序遍历是指先遍历根，在遍历左子树，最后遍历右子树。做二叉树相关的题目比较简单的思路一般就是使用递归，同样这题我们也使用递归来遍历二叉树。

在这里插入图片描述
list.add(root.val)
在这里插入图片描述

在这里插入图片描述
在这里插入图片描述

在这里插入图片描述
在这里插入图片描述

在这里插入图片描述
root为null时，返回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 List<Integer> preorderTraversal(TreeNode root) {
    //因为题目要求我们返回List<Integer>类型，所以我们创建一个list
        List<Integer> list = new ArrayList<>();
        //递归结束的条件
        if(root == null) {
            return list;
        }
        //先遍历根结点
        list.add(root.val);
        //左子树
        List<Integer> leftTree = preorderTraversal(root.left);
        list.addAll(leftTree);
        //右子树
        List<Integer> rightTree = preorderTraversal(root.right);
        list.addAll(rightTree);

        return list;
    }
}

在这里插入图片描述

2.二叉树的中序遍历

leetcode之二叉树的中序遍历（难度：简单）

做题思路

二叉树的中序遍历跟二叉树的前序遍历思路是一样的，不同的只是遍历的顺序，中序遍历是先遍历左子树，然后是根节点，再就是右子树。

代码实现

/**
 * 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 List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root == null) {
            return list;
        }
        List<Integer> leftTree = inorderTraversal(root.left);
        list.addAll(leftTree);
        list.add(root.val);
        List<Integer> rightTree = inorderTraversal(root.right);
        list.addAll(rightTree);

        return list;
    }
}

在这里插入图片描述

3.二叉树的后序遍历

leetcode之二叉树的后序遍历（难度：简单）

做题思路

二叉树的后序遍历是先遍历左子树，然后是右子树，最后是根节点

代码实现

/**
 * 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 List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root == null) {
            return list;
        }
        List<Integer> leftTree = postorderTraversal(root.left);
        list.addAll(leftTree);
        List<Integer> rightTree = postorderTraversal(root.right);
        list.addAll(rightTree);
        list.add(root.val);

        return list;
    }
}

在这里插入图片描述

4.相同的树

leetcode之相同的树（难度：简单）

题目要求

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

示例

在这里插入图片描述

输入：p = [1,2,3], q = [1,2,3]
输出：true

/**
 * 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 isSameTree(TreeNode p, TreeNode q) {
}

做题思路

这个题我们可以先判断两个树的结构是否相同，如果结构相同我们就判断对应位置的数据是否相同，我们判断的顺序是先判断根节点，然后是左子树，再是右子树。

代码实现

/**
 * 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 isSameTree(TreeNode p, TreeNode q) {
    //当q或者p其中有一个为null时，我们就需要判断两个树的结构是否相同
        if(p == null || q == null) {
        //都为null则表示结构相同
            if(p == null && q == null) {
                return true;
            }else {
                return false;
            }
        }
        //判断根结点的数据是否相同
        if(p.val != q.val) {
            return false;
        }
        return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
    }
}

在这里插入图片描述

5.另一颗树的子树

leetcode之另一棵树的子树（难度：简单）

题目要求

给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。

二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。

/**
 * 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 isSubtree(TreeNode root, TreeNode subRoot) {

    }
}

示例

在这里插入图片描述
输入：root = [3,4,5,1,2], subRoot = [4,1,2]
输出：true

做题思路

我们做这个题需要用到前面的判断两个树是否相等，我们判断root是否有跟subRoot这个树相同的子树。

代码实现

/**
 * 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 isSametree(TreeNode p,TreeNode q) {
        //判断结构是否相同
        if(p == null || q == null) {
            if(p == null && q == null) {
                return true;
            }else {
                return false;
            }
        }
        if(p.val != q.val) {
            return false;
        }
        return isSametree(p.left,q.left) && isSametree(p.right,q.right);
    }

    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
    //当root遍历到空时说明root的左子树或者右子树中没有subRoot，返回fasle
        if(root == null) {
            return false;
        }
        //判断root整个树是否跟subRoot相同
        if(isSametree(root,subRoot)) {
            return true;
        }
        //判断左子树和右子树中是否含有subRoot
        return isSubtree(root.left,subRoot) || isSubtree(root.right,subRoot);
    }
}

在这里插入图片描述

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

leetcode刷题

java学习

LeetCode

算法

数据结构

leetcode刷题（7）二叉树（1） 的相关文章

随机推荐

  • Android Log-日志介绍

    一 基本介绍 Logcat是Android日常开发过程中的重要组成部分 Logcat上会显示系统消息 使用Log类添加到应用的消息 应用运行异常信息等 通过日志 我们可以实时监控应用运行状态 为应用调试提供重要参考 Log格式 一条标准的日

  • Appium抓取app数据

    主流APP数据抓取难点 1 请求参数加密 sign签名 使用sha1加上md5做辅助加密 2 请求body加密 整个请求体使用DES算法做加解密 3 代理检测反爬 抓包设置代理后 直接不再加载数据 4 私有CA证书反爬 由于公有的证书需要付

  • Scala中sorted、sortBy、sortWith区别

    1 sorted方法真正排序的逻辑是调用的java util Arrays sort 源码 def sorted B gt A implicit ord Ordering B Repr val len this length val b n

  • UG NX10.0软件安装教程

    软件下载 名称 UG NX 10 0 语言 简体中文 安装环境 Windows 下载链接 链接 https pan baidu com s 1SkskLU2CYLQznfGWM7O4HQ 提取码 ersv 安装中有问题请咨询管家微信 don

  • Android面试题最新整理，2022年最新版

    每年的9月和10月 是互联网大厂疯狂招人的时期 也是程序员们跳槽的黄金期 不知道你有没有幻想过这样一个场景 大厂的面试官说 恭喜你通过面试 明天来办理入职吧 今天 为大家整理了2022年Android大厂面试真题 刷企业历年真题 助你轻松搞

  • 大话西游手游有双系统服务器吗,大话西游手游有几个版本_大话西游手游官服和混服怎么区分_玩游戏网...

    大话西游 手游时间服点卡是互通的吗 点卡有两种 一种是大话西游手游内部的点卡 这种点数是在游戏里面购买道具或者计时用的 分为绑定点和交易点 这种是不能通用的 比如我在时间服有两个号 一个是绝代佳人区 另外一个是勿忘初心区 绝代佳人的点卡是不

  • 基于Matlab实现图像融合技术（附上多个仿真源码+数据）

    图像融合技术是一种将多幅图像融合为一幅图像的方法 使得这幅融合图像包含原始图像的所有信息 近年来 图像融合技术已经广泛应用于图像分割 变换和裁剪等领域 本文将介绍如何使用Matlab实现图像融合技术 实现步骤 首先 我们需要了解图像融合的基

  • linux下c语言实现tail -f功能---实时读取变化文件中的增量内容

    最近由于项目需要 需要对文件中实时新增的数据进行处理 结合tail f的逻辑 用c语言实现了这一功能 代码如下 cpp view plain copy include

  • jquery获取select值

  • ARM架构学习（二）——流水线

    本期主题 ARM流水线 往期地址 ARMv7架构学习 ARM流水线 1 流水线概念 2 指令的分解步骤 1 流水线概念 硬件资源总是有限的 有一个明显的方法能改善硬件资源的利用率 这就是pipeline 流水线 技术 其实就是在当前指令结束

  • std::nth_element bug引起的crash问题

    1 源码 auto less compare const MirroringGroup mg1 const MirroringGroup mg2 gt bool return mg1 usage lt mg2 usage std nth e

  • 腾讯云服务器配置选择方法

    腾讯云服务器配置如何选择 CPU内存 带宽和系统盘怎么选择合适 个人用户可以选择轻量应用服务器 企业用户可以选择云服务器CVM 2核2G3M带宽轻量服务器95元一年 2核4G5M服务器168元一年 企业用户可以选择标准型S5云服务器 可以一

  • idea 生成类图

    选中类 ctrl alt u或者ctrl alt shift u 生成类图

  • ArcGIS GraphicsLayer层的特殊要求

    如果你要使用GraphicsLayer这个绘图层 那么你需要注意自己的布局的模式不可以使用 layout absolute 如果你使用了这个布局 那么你的GraphicsLayer层可能会无法使用 比如下面的程序就是因为设置了 layout

  • java 最大公约数和最小公倍数

    题目 题目 输入两个正整数m和n 求其最大公约数和最小公倍数 比如 12和20的最大公约数是4 最小公倍数是60 说明 break关键字的使用 代码一 package l2 for 题目 输入两个正整数m和n 求其最大公约数和最小公倍数 比

  • Counter统计列表中元素出现次数

    使用Counter方法 统计元素在列表中出现的次数 from collections import Counter k labels 1 1 0 1 0 0 1 1 2 2 3 2 2 2 2 Counter返回的是字典 key为列表中元素

  • TVM系列---1.开始使用Tensor Expression

    Author Tianqi Chen https docs tvm ai tutorials tensor expr get started html Tensor Expression入门 这是TVM中Tensor表达语言的入门教程 TV

  • Unity动画系统详解5：BlendTree混合树是什么？

    摘要 Animator中有一个功能 用来解决多个动画之间的混合 经常用于移动动画之间的混合 这个功能叫做BlendTree 混合树 洪流学堂 让你快人几步 你好 我是跟着大智学Unity的萌新 我叫小新 这几周一起来复 yu 习 xi 动画

  • cl : 命令行 warning D9002：忽略未知选项“ /NODEFAULTLIB:library ”

    前言 cl 命令行 warning D9002 忽略未知选项 NODEFAULTLIB library 原因 一下引用 連結器工具警告 LNK4098 执行运行时程序库现在包含指示词 以防止混合不同的类型 如果您尝试在相同的程序中使用不同类

  • leetcode刷题（7）二叉树（1）

    哈喽大家好 这是我leetcode刷题的第七篇 这两天我将更新leetcode上关于二叉树方面的题目 如果大家对这方面感兴趣的话 欢迎大家持续关注 谢谢大家 那么我们就进入今天的主题 文章目录 1 二叉树的前序遍历 题目要求 示例 做题思路

热门标签