考察的知识点：栈的基本操作；解答方法分析：创建一个整数类型的栈 nums，用于存储计算结果或中间结果。定义一个整数变量 num，用于存储当前数字的值。定义一个字符变量 op，用于存储当前操作符。遍历输入的字符串 s，对每个字符进行。如果当前字符是数字，则将其与 num 相乘并更新 num 的值。如果当前字符是左括号 ( 则找到与之匹配的右括号 ) 的位置，并将括号内的子字符串作为新的表达式计算结果，并更新 num 的值。如果当前不为空格，或者已经遍历到字符串末尾，则进行计算。根据上一个操作符 op 的值，分别执行加法、减法乘法操作。将计算结果存入栈 nums。将 num 重置为0，且将当前字符...

考察的知识点：栈的基本操作、后缀表达式；解答方法分析：如果元素是一个操作符（“+”, “-”, “*”, “/”），则从栈st中弹出两个元素，分别表示操作数num2和num1。然后，根据操作符计算出结果并将结果压入栈st中。如果元素是一个数字，则将其转换为整型并将其压入栈st中。最后，返回结果。所用编程语言：C++；完整编程代码：↓ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param tokens string字符串vector * @return int整型 */ int calcu...

考察的知识点：栈的基本操作和字符匹配；解答方法分析：创建一个栈用于存储左括号。栈的作用是用于判断括号的闭合性，它遵循先进后出的原则。每当遇到左括号时，就将其压入栈中，当遇到右括号时，就需要判断当前栈顶的左括号是否与之匹配。遍历字符串s的每个字符。在遍历过程中，对于每个字符，我们需要判断它是否是左括号或右括号，并进行相应的操作。如果当前字符是左括号（‘(’, ‘{’, ‘[’），将其压入栈中。如果当前字符是右括号（‘)’, ‘}’,‘]’），我们需要判断栈是否为空。如果栈为空，说明没有相应的左括号与之匹配，直接返回false。如果栈不为空，将栈顶的左括号弹出，判断当前右括号是否与弹出的左括号匹配...

考察的知识点：MaxCowStack 类的实现、栈；解答方法分析：MaxCowStack操作将栈s和maxStack清空，并将结果数组res的当前位置设置为-1。push操作将vals[i][1压入栈s，并更新maxStack的值。如果maxStack为空，则将vals[i][1]也压入maxStack；否则，比较maxStack的栈顶元素和vals[i][1]的大小，将较大的压入maxStack。pop操作将栈s和maxStack的栈顶元素出栈，并将结果数组res的当前位置设置为-1。top操作返回栈s的栈顶元素，并将其赋值给结果数组res的当前位置。getMax操作返回maxStack栈顶...

考察的知识点：二叉树的递归遍历；解答方法分析：定义了一个Solution类，其中有一个公有成员函数pathSum，用于计算二叉树中路径和等于给定值的路径数量。pathSum函数使用了递归的方法，首先判断当前节点是否为空，如果为空则返回0。如果当前节点的值等于给定的sum值，计数器count加1。递归调用pathSum函数计算左子树和右子树的路径和等于sum的路径数量，并将结果累加到count中。最后返回count作为结果。所用编程语言：C++；完整编程代码：↓ /** * struct TreeNode { * int val; * struct TreeNode *left; * struc...

考察的知识点：二叉树的递归遍历；解答方法分析：首先，在diameterOfBinaryTree函数中，需要定义一个变量diameter用于记录最大路径长度，并初始化为0。然后，在递归函数depth中，对当前节点进行处理：如果当前节点为空，返回0。否则，递归求解当前节点的左子树的高度和右子树的高度，并分别赋值给left和right。计算当前节点为根节点时的路径长度，即左子树高度和右子树高度之和，并将其与diameter比较，更新diameter的值。返回以当前节点为根节点的子树的最大高度，即左子树高度和右子树高度的较大值加1。最后，在主函数中调用depth函数，并返回最大路径长度diameter...

考察的知识点：二叉树的递归遍历；解答方法分析：首先，如果当前根节点为空或者当前根节点的值等于p或q的值，直接返回当前根节点的值或-1。然后，递归调用lowestCommonAncestor函数，在根节点的左子树和右子树中查找最近公共祖先节点。根据递归的结果进行判断，如果左子树的结果为-1，说明p和q都在右子树中，返回右子树的结果。如果右子树的结果为-1，说明p和q都在左子树中，返回左子树的结果。如果左子树和右子树的结果都不为-1，则说明p和q分别位于当前根节点的左右子树中，当前根节点就是最近公共祖先节点，返回当前根节点的值。所用编程语言：C++；完整编程代码：↓ /** * struct Tr...

考察的知识点：二叉搜索树、深度优先搜索；解答方法分析：定义一个递归函数rangeSum，接收一个指向根节点的指针参数root以及区间的最小值low和最大值high，并返回区间内所有节点值的和。在rangeSum函数中，首先判断根节点root是否为空。若为空，则返回0，表示当前子树无节点。接着判断根节点的值是否在区间范围内。若不在范围内，则继续递归遍历左子树（当root->val > high时）或右子树（当root->val < low时），并返回子树内节点值的和。若根节点的值在区间范围内，则将根节点的值加入结果中，然后继续递归遍历左子树和右子树，将它们返回的值累加到结...

考察的知识点：二叉树的中序遍历；解答方法分析：定义一个递归函数inorder，接收一个指向根节点的指针参数root和一个指向整型数组的引用参数result。该函数将按照中序遍历的顺序遍历并存储以root为根节点的二叉树的值。在inorder函数中，首先判断根节点root是否为空。若为空，则直接返回。递归调用inorder函数遍历root的左子树，即inorder(root->left, result)。将root的值存入result数组中，即result.push_back(root->val)。递归调用inorder函数遍历root的右子树，即inorder(root->r...

考察的知识点：二叉树的递归遍历；解答方法分析：定义一个递归函数countNodes，接收一个指向根节点的指针参数root，返回以root为根节点的二叉树的节点个数。在countNodes函数中，首先判断根节点root是否为空。如果为空，说明该二叉树为空树，节点个数为0。如果根节点不为空，则递归计算左子树的节点个数，记为leftCount，递归计算右子树的节点个数，记为rightCount。最后将左子树节点个数、右子树节点个数和根节点相加，得到以root为根节点的二叉树的节点个数。返回节点个数。所用编程语言：C++；完整编程代码：↓ /** * struct TreeNode { * int v...

考察的知识点：二叉树的中序遍历；解答方法分析：创建一个虚拟节点dummy，用来保存展开后链表的头节点。创建一个指针curr，用来指向当前链表的末尾。创建一个栈stk，用来模拟递归的过程。初始化一个指针node，指向根节点root。进入循环，当node不为空或者栈不为空时：先遍历左子树，将所有子节点依次压入栈中，直到叶子节点为止。弹出栈顶的节点，表示该节点的左子树已经处理完毕。将该节点链接到curr的右侧，同时将节点的左子节点置为空。更新curr为当前节点。继续处理右子树，令node指向当前节点的右子节点。返回dummy节点的右子节点，即为展开后的链表。所用编程语言：C++；完整编程代码：↓ /...

考察的知识点：二叉树的展开；解答方法分析：首先判断根节点是否为空，如果为空，则直接返回。使用迭代的方式，从根节点开始遍历二叉树。对于每个节点，如果存在左子树，则找到左子树最右侧的节点，并将其右子树连接到该节点后面。将当前节点的右子树指针指向左子树，并将左子树指针置为空。移动当前节点指针到下一个节点，继续执行2-4步骤，直到遍历完整个二叉树。返回展开后的二叉树的根节点。所用编程语言：C++；完整编程代码：↓ /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNod...

考察的知识点：二叉树的构建和遍历；解答方法分析：在buildTree函数中，首先判断输入数组是否为空或长度不相等，如果是，则返回空指针。调用buildTreeHelper函数进行具体的构建操作。在buildTreeHelper函数中，参数inOrder表示中序遍历的数组，参数inStart和inEnd表示当前处理中序遍历数组的起始和结束位置，postOrder表示后序遍历的数组，参数postStart和post表示当前处理后序遍历数组的起始位置和结束位置。首判断递归结束的条件，即inStart大于inEnd或postStart大于postEnd，如果是，则返回空指针。获取当前子树的根节点值，即...

考察的知识点：二叉树的构造和遍历；解答方法分析：在buildTree函数中，首先判断输入数组是否为空或长度不相等，如果是，则返回空指针。调用buildTreeHelper函数进行具体的构建操作。在buildTreeHelper函数中，参数inOrder表示中序遍历的数组，参数inStart和inEnd表示当前处理中序遍历数组的起始和结束位置。4.postOrder表示后序遍历的数组，参数postStart和post表示当前处理后序遍历数组的起始位置和结束位置。首判断递归结束的条件，即inStart大于inEnd或postStart大postEnd，如果是，则返回空指针。获取当前子树的根节点值，...