前言

😊 大家好，我是作家桑。这是自己的一个 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<int> tmp = new List<int>();
    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<int> myList = new List<int>();

        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<int> inStack;
    Stack<int> outStack; 

    public CQueue()
    {
        inStack = new Stack<int>();
        outStack = new Stack<int>();
    }

    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 栈顶的整数即可