94.二叉树的中序遍历

LeetCode LeetCode 树深度优先搜索广度优先搜索栈

发布时间 : 2000-01-10 00:09

字数:1.2k 阅读 :

评论:

94.二叉树的中序遍历

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 题解

递归中序遍历

// 方法一：递归中序遍历
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;
}

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