94.二叉树的中序遍历

LeetCode LeetCode 热题100 树 深度优先搜索 广度优先搜索 栈
发布时间 :
字数:1.6k 阅读 : 评论:
  1. 94.二叉树的中序遍历
    1. 94.1 题目
    2. 94.2 题解
      1. 方法一：递归中序遍历
        1. 思路
        2. 复杂度分析
        3. 代码
      2. 方法二：迭代中序遍历
        1. 思路
        2. 复杂度分析
        3. 代码
    3. 94.3 代码
    4. 94.4 运行结果

94.二叉树的中序遍历

94.1 题目

给定一个二叉树的根节点 root，返回它的中序遍历。

示例 1：

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

示例 2：

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

示例 3：

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

提示：

  • 树中节点数目在范围 [0, 100] 内
  • -100 <= Node.val <= 100

进阶：

递归算法很简单，你可以通过迭代算法完成吗？

94.2 题解

方法一：递归中序遍历

思路

中序遍历的顺序是：左子树 → 根节点 → 右子树。递归实现最直观：先递归遍历左子树，访问当前节点，再递归遍历右子树。使用辅助函数保存遍历结果。

核心思想：递归实现左-根-右的遍历顺序。

具体步骤：

  1. 如果当前节点为空，返回。
  2. 递归遍历左子树。
  3. 访问当前节点，将值加入结果列表。
  4. 递归遍历右子树。

举例：对于 root = [1,null,2,3]：

  • 节点 1：左子树为空，访问 1，递归右子树
  • 节点 2：递归左子树
  • 节点 3：左子树为空，访问 3，右子树为空
  • 回到节点 2：访问 2
  • 结果：[1,3,2]

复杂度分析

  • 时间复杂度：O(n)，每个节点访问一次。
  • 空间复杂度：O(h)，递归栈深度为树的高度，最坏情况为 O(n)。

代码

// 方法一：递归中序遍历
static List<int> InorderTraversal1(TreeNode root)
{
    // 创建一个列表来存储中序遍历的结果
    List<int> result = new List<int>();

    // 调用递归辅助函数进行中序遍历
    InorderTraversalHelper1(root, result);

    // 返回中序遍历的结果列表
    return result;
}

// 递归辅助函数，用于实现中序遍历
static void InorderTraversalHelper1(TreeNode node, List<int> result)
{
    // 如果当前节点不为空，继续递归遍历左子树、访问当前节点值、递归遍历右子树
    if (node != null)
    {
        InorderTraversalHelper1(node.left, result);
        result.Add(node.val);
        InorderTraversalHelper1(node.right, result);
    }
}

方法二：迭代中序遍历

思路

用栈模拟递归过程。

先一直向左走，将路径上的节点入栈。当无法继续向左时，弹出栈顶节点访问，然后转向右子树。

重复上述过程直到栈为空且当前节点为空。

举个例子：

    1
     \
      2
     /
    3
  • current=1，入栈1，current=null
  • 弹出1，访问1，current=2
  • 入栈2，入栈3，current=null
  • 弹出3，访问3，current=null
  • 弹出2，访问2
  • 结果：[1,3,2]

复杂度分析

  • 时间复杂度：O(n)
  • 空间复杂度：O(h)，栈深度

代码

// 方法二：迭代中序遍历
static List<int> InorderTraversal2(TreeNode root)
{
    // 创建一个列表来存储中序遍历的结果
    List<int> result = new List<int>();

    // 创建一个栈来辅助迭代中序遍历
    Stack<TreeNode> stack = new Stack<TreeNode>();

    // 初始化当前节点为根节点
    TreeNode current = root;

    // 当当前节点不为空或者栈不为空时，继续迭代
    while (current != null || stack.Count > 0)
    {
        // 遍历左子树，将节点入栈，只要左子树不为空一直压入栈中
        while (current != null)
        {
            // 将当前节点入栈
            stack.Push(current);

            // 切换到左子树
            current = current.left;
        }

        // 出栈节点，访问
        current = stack.Pop();

        // 将当前节点的值添加到结果列表
        result.Add(current.val);

        // 切换到右子树
        current = current.right;
    }

    // 返回中序遍历的结果列表
    return result;
}

94.3 代码

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        #region 题目

        // 给定一个二叉树的根节点 root ，返回 它的中序遍历。

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

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

        // 示例 3：
        // 输入：root = [1]
        // 输出：[1]

        // 提示：
        // 树中节点数目在范围 [0, 100] 内
        // -100 <= Node.val <= 100

        // 进阶: 递归算法很简单，你可以通过迭代算法完成吗？

        #endregion

        #region 测试

        // 示例 1
        TreeNode root1 = new TreeNode(1, null, new TreeNode(2, new TreeNode(3), null));
        List<int> result1 = InorderTraversal1(root1);
        Console.WriteLine($"示例1 方法1 输出：{string.Join(", ", result1)}");
        List<int> result1_2 = InorderTraversal2(root1);
        Console.WriteLine($"示例1 方法2 输出：{string.Join(", ", result1_2)}");

        // 示例 2
        TreeNode root2 = null;
        List<int> result2 = InorderTraversal1(root2);
        Console.WriteLine($"示例2 方法1 输出：{string.Join(", ", result2)}");
        List<int> result2_2 = InorderTraversal2(root2);
        Console.WriteLine($"示例2 方法2 输出：{string.Join(", ", result2_2)}");

        // 示例 3
        TreeNode root3 = new TreeNode(1);
        List<int> result3 = InorderTraversal1(root3);
        Console.WriteLine($"示例3 方法1 输出：{string.Join(", ", result3)}");
        List<int> result3_2 = InorderTraversal2(root3);
        Console.WriteLine($"示例3 方法2 输出：{string.Join(", ", result3_2)}");

        #endregion
    }

    #region 答案

    // 方法一：递归中序遍历
    static List<int> InorderTraversal1(TreeNode root)
    {
        // 创建一个列表来存储中序遍历的结果
        List<int> result = new List<int>();

        // 调用递归辅助函数进行中序遍历
        InorderTraversalHelper1(root, result);

        // 返回中序遍历的结果列表
        return result;
    }

    // 递归辅助函数，用于实现中序遍历
    static void InorderTraversalHelper1(TreeNode node, List<int> result)
    {
        // 如果当前节点不为空，继续递归遍历左子树、访问当前节点值、递归遍历右子树
        if (node != null)
        {
            InorderTraversalHelper1(node.left, result);
            result.Add(node.val);
            InorderTraversalHelper1(node.right, result);
        }
    }


    // 方法二：迭代中序遍历
    static List<int> InorderTraversal2(TreeNode root)
    {
        // 创建一个列表来存储中序遍历的结果
        List<int> result = new List<int>();

        // 创建一个栈来辅助迭代中序遍历
        Stack<TreeNode> stack = new Stack<TreeNode>();

        // 初始化当前节点为根节点
        TreeNode current = root;

        // 当当前节点不为空或者栈不为空时，继续迭代
        while (current != null || stack.Count > 0)
        {
            // 遍历左子树，将节点入栈，只要左子树不为空一直压入栈中
            while (current != null)
            {
                // 将当前节点入栈
                stack.Push(current);

                // 切换到左子树
                current = current.left;
            }

            // 出栈节点，访问
            current = stack.Pop();

            // 将当前节点的值添加到结果列表
            result.Add(current.val);

            // 切换到右子树
            current = current.right;
        }

        // 返回中序遍历的结果列表
        return result;
    }

    #endregion
}

class TreeNode
{
    public int val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null)
    {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

94.4 运行结果

示例1 方法1 输出：1, 3, 2
示例1 方法2 输出：1, 3, 2
示例2 方法1 输出：
示例2 方法2 输出：
示例3 方法1 输出：1
示例3 方法2 输出：1
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com

赏

©2016-2026 Tao

Built with Hexo and 3-hexo theme

×

喜欢就点赞,疼爱就打赏