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

🕗 发布于 2025-01-15 02:01 leetcode javascript 算法

题目：

在这里插入图片描述

二叉树：

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

‌先序遍历（前序遍历）‌：

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

中序遍历‌：

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

后序遍历‌：

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

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

题解-举例

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

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

通过：