文章目录

• 前言
• 关于编译环境
• 06. 从尾到头打印链表
• 07. 重建二叉树
• 09. 用两个栈实现队列
• 结语

前言

😊 大家好，我是作家桑。这是自己的一个 C# 做题记录，方便自己学习的同时分享出来。

关于编译环境

注意，笔者使用的编译环境是 .NET 7 和 C# 11。

06. 从尾到头打印链表

题目描述：

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

示例：

输入：head = [1,3,2]
输出：[2,3,1]

代码实现：

/*** Definition for singly-linked list.* public class ListNode {*     public int val;*     public ListNode next;*     public ListNode(int x) { val = x; }* }*/public class Solution
{List tmp = new List();int count = 0;          // 用于计算链表中的节点个数 public int[] ReversePrint(ListNode head){reversal(head);int[] res = new int[count];for (int i = 0; i < res.Length; i++){res[i] = tmp[i];}return res;}public void reversal(ListNode head) {// 递归 if (head == null) return;reversal(head.next);tmp.Add(head.val);count++;}
}

运行结果：

思路讲解：

• 首先创建一个临时列表 tmp 和整数 count 分别用于存放链表节点和节点个数
• 自定义一个 reversal 方法， 使用递归将链表中的节点从尾到头依次放入 tmp 列表
• 循环遍历 tmp 列表中的元素赋值给新创建的 res 数组，循环结束后直接返回 res 即可

代码实现2：

/*** Definition for singly-linked list.* public class ListNode {*     public int val;*     public ListNode next;*     public ListNode(int x) { val = x; }* }*/public class Solution {public int[] ReversePrint(ListNode head) {List myList = new List();while (head != null){myList.Add(head.val);head = head.next;}myList.Reverse();return myList.ToArray();}
}

运行结果2：

思路讲解：

• 创建一个整数列表 myList，循环遍历链表中的节点并放入其中
• 循环结束时，使用 Reverse 方法反转整个 myList 列表
• 使用 ToArray 方法将列表 myList 转换为数组后直接返回即可

07. 重建二叉树

题目描述：

输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

示例：

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]

代码实现：

public class TreeNode
{public int val;public TreeNode left;public TreeNode right;public TreeNode(int x) { val = x; }
}public class Solution
{public TreeNode BuildTree(int[] preorder, int[] inorder){int n = preorder.Length;if (n == 0) return null;if (n == 1) return new TreeNode(preorder[0]);TreeNode root = new TreeNode(preorder[0]);      // 树节点 int index = Array.IndexOf(inorder, root.val);root.left = BuildTree(preorder[1..(index + 1)], inorder[..index]);      // 左子树root.right = BuildTree(preorder[(index + 1)..], inorder[(index+1)..]);      // 右子树return root; }
}

运行结果：

思路讲解：

• 创建变量 n 确定前序数组的长度，当 n 为0时直接返回，当 n 为1时表示只有先序遍历中的第一个节点为根节点可以直接返回
• 创建根节点 root 和整数变量 index 表示根节点在中序数组中的位置
• 求解二叉树的左右子树，根据根节点在中序遍历中的位置，位置左边的为左子树，位置右边的为右子树。如果根节点位置左边或右边为空，则该方向的子树为空；如果根节点左右两边均为空，则根节点为叶子节点
• 采用递归方法，对二叉树的左、右子树重重复前面的步骤，直到获得二叉树

09. 用两个栈实现队列

题目描述：

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )

示例：

输入：
[“CQueue”,“appendTail”,“deleteHead”,“deleteHead”,“deleteHead”]
[[],[3],[],[],[]]
输出：[null,null,3,-1,-1]

代码实现：

public class CQueue
{Stack inStack;Stack outStack; public CQueue(){inStack = new Stack();outStack = new Stack();}public void AppendTail(int value){inStack.Push(value);}public int DeleteHead(){if(outStack.Count == 0){if(inStack.Count == 0)      // 没有元素可以删除了 return -1;          while (inStack.Count > 0)   // 把inStack栈内的所有元素放到outStack栈内outStack.Push(inStack.Pop());}return outStack.Pop();}
}

运行结果：

思路讲解：

• 分别创建两个栈类型 inStack 和 outStack 用于队列的插入整数和删除整数
• 当队列中插入整数时，调用 AppendTail 方法中 inStack.Push 方法添加指定整数 value
• 当队列中删除整数时，调用 DeleteHead 方法。其中当 outStack 和 inStack 栈内都为空时，返回-1；当 outStack 栈内为空但是 inStack 栈内不为空时，使用 while 循环将 inStack 栈内的所有整数添加到 outStack 栈中，然后返回 outStack 栈顶的整数即可

结语

🌻 以上就是本次的做题记录啦，希望大家看完有所收获。