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
