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

LeetCode热题100-二叉树的中序遍历【JavaScript讲解】

题目:

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

二叉树:

二叉树的遍历是指按照某种特定的顺序访问二叉树中的每个节点,使得每个节点被访问且仅被访问一次。二叉树的遍历主要分为三种:先序遍历(前序遍历)、中序遍历和后序遍历。

‌先序遍历(前序遍历)‌:

遍历顺序:根节点 -> 左子树 -> 右子树。
在先序遍历中,首先访问的是根节点,然后递归地先序遍历左子树,最后递归地先序遍历右子树。

中序遍历‌:

遍历顺序:左子树 -> 根节点 -> 右子树。
在中序遍历中,首先递归地中序遍历左子树,然后访问根节点,最后递归地中序遍历右子树。这种遍历方式也被称为对称遍历。

后序遍历‌:

遍历顺序:左子树 -> 右子树 -> 根节点。
在后序遍历中,首先递归地后序遍历左子树,然后递归地后序遍历右子树,最后访问根节点。

对于任意给定的二叉树,我们都可以通过递归或迭代的方式实现这三种遍历。

题解-举例

       A
      / \
     B   C
    / \
   D   E

现在,我们按照中序遍历的规则来遍历这棵树:

1‌.首先遍历左子树‌:

从根节点A开始,我们先看它的左子树,即节点B。
节点B也有左子树和右子树,我们先遍历它的左子树,即节点D。
节点D没有子树,所以它是第一个被访问的节点。

2‌.然后访问根节点‌:

访问完节点D后,我们回到它的父节点B,并访问B。
接着,我们访问节点B的右子树,即节点E。

3.最后遍历右子树‌:

访问完节点B及其所有子树后,我们回到最初的根节点A,并访问A的右子树,即节点C。
按照上述步骤,中序遍历的顺序是:D -> B -> E -> A -> C。

代码解题-方法一:递归法

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function(root) {
    if(root == null) return [];
    let result = [];
    result = result.concat(inorderTraversal(root.left));
    result.push(root.val);
    result  = result.concat(inorderTraversal(root.right));
    return result;
};

concat 函数通常用于连接两个或多个字符串、数组、列表或其他类似的数据结构,形成一个新的、包含所有输入元素的结构。

代码解题-方法二:迭代法

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function(root) {
    let result = [];
    let stk = [];
    while(root || stk.length){
        while(root){
            stk.push(root);
            root = root.left;
        }

        root = stk.pop();
        result.push(root.val);

        root = root.right;
    }
    return result;
};

通过:

在这里插入图片描述


http://www.kler.cn/a/505589.html

相关文章:

  • 工作记录小点
  • 4G DTU赋能智能配电环网柜通信运维管理
  • Docker
  • java.net.SocketException: Connection reset 异常原因分析和解决方法
  • Openresty 安装
  • 微信小程序集成Vant Weapp移动端开发的框架
  • 11-1.Android 项目结构 - androidTest 包与 test 包(单元测试与仪器化测试)
  • 【C】数组和指针的关系
  • Ubuntu 安装和配置 MariaDB
  • 【行空板K10】上传温湿度信息到EasyIoT平台
  • redis闪退打不开Creating Server TCP listening socket *:6379: listen: Unknown error
  • ESP8266固件烧录
  • 利用Python爬虫按图搜索1688商品(拍立淘)的探索之旅
  • 从CRUD到高级功能:EF Core在.NET Core中全面应用(二)
  • 鸿蒙报错Init keystore failed: keystore password was incorrect
  • 【element plus】虚拟dom表格中cellRenderer如何使用v-for循环渲染item
  • 【vue3】 defineExpose 的使用
  • IIO(Industrial I/O)驱动介绍
  • 使用分割 Mask 和 K-means 聚类获取天空的颜色
  • 爬虫后的数据处理与使用(使用篇--实现分类预测)
  • css 三角构建
  • MCU中实时时钟(RTC)和普通定时器有什么区别
  • 深入Android架构(从线程到AIDL)_32 JNI架构原理_Java与C的对接05
  • C -- 大端对齐 小端对齐 的人性化解释
  • HTTP 缓存机制详解
  • matlab专栏-M文件