牛客786963925号

题解

/ 注册

全部文章 / 题解（共10篇）

题解 | #序列化二叉树#

解法一：前序遍历题目要求：1. 访问二叉树，并将访问结果存到一个字符串中返回，即：「二叉树的序列化」；2. 访问得到的字符串，重构出二叉树，即：「二叉树的反序列化」。显而易见的是，在二叉树的序列化过程中，需要「遍历二叉树」，因此可采用二叉树的遍历方法之一：「前序遍历」来实现。这是因为：前序遍历是...

C++ 二叉树先序遍历层次遍历队列递归

2021-08-08

0 555

题解 | #正则表达式匹配#

解法一：动态规划与此题类似，此题可以采用动态规划的方法来求解。定义二维递推数组dp，其中表示字符串str的前个字符与字符串pattern的前个字符是否匹配（设dp数组行、列分别为、，其中分别为字符串str和pattern的长度）。「动态规划算法的关键是确定递推式」，对于此题有如下几种情况：（为方...

动态规划 C++ 递归

2021-07-31

11 1015

题解 | #未排序数组中累加和为给定值的最长子数组长度#

解法一：回溯 + set 利用回溯方法进行求解的思路如下：（具体递归过程见图示）对于每一个位置，都有「选」和「不选」两种可能，因此需要定义一个state数组用来记录「当前元素是否已经被选择」；字符串cur用来记录「当前」字符串的情况，在每次递归时，在cur末尾加上当前字符（若其未被选择过），然...

C++ 回溯递归 set

2021-07-25

3 572

题解 | #数独#

解法一：解法一的思路较为直接：对数独中的每个位置，若其不为.，即没有被数字所填，则从数字1至9遍历，分别填写该位置，并检验此时数独是否有效。若成功填满最后一个位置，即是该数独的解，否则将填写的位置重置，继续遍历。解法一的思路如图所示。在「检验数独」是否有效时，需要如下3个步骤：检验数独...

C++ 回溯递归

2021-07-17

4 1018

题解 | #实现二叉树先序，中序和后序遍历#

解法一：递归「二叉树的先序遍历」的思路是：先访问根结点，再访问左子树，最后访问右子树；「二叉树的中序遍历」的思路是：先访问左子树，再访问根结点，最后访问右子树；「二叉树的后序遍历」的思路是：先访问左子树，再访问右子树，最后访问根结点；下图以「先序遍历」为例进行展示：基于上述思路，可以得...

C++ 二叉树中序遍历先序遍历后序遍历递归栈

2021-07-14

20 2109

题解 | #加起来和为目标值的组合#

利用set解法对于此题，可以利用「回溯」的思想求解：先尝试某一选择，若满足题目条件，则加到最终结果中；否则撤销该选择，重新进行下一次选择。具体而言，利用「回溯」算法求解此题的步骤如图所示：对于原数组，从第一个位置（为10）开始选，加入到临时数组arr中，并将目前的求和结果加入到cur...

C++ 递归回溯

2021-07-13

8 1091

题解 | #平衡二叉树#

解法一：自顶向下一棵二叉树为「平衡二叉树」的条件为：该树为空树，或者其左右子树的高度差最大为1。因此，判断一棵二叉树是否平衡需要求其子树高度，并比较左右子树高度差。因此此题的解题步骤如下：设计「求二叉树高度」的函数getHeight(root)，作用是求以root为根结点的二叉树高度；遍历...

二叉树 C++ 递归平衡二叉树

2021-07-12

8 1185

题解 | #判断一棵二叉树是否为搜索二叉树和完全二叉树#

解法一：中序遍历（递归）+ 层次遍历一棵「二叉搜索树」需要满足要求：对于每个结点，左子树上的所有结点小于它，右子树上的所有结点大于它。判断一棵二叉树是否为「二叉搜索树」的通用方法为：对该二叉树进行中序遍历，若遍历结果为「严格」单调递增的，则是一棵二叉搜索树，否则不是。这是因为：中序遍历的步骤是...

C++ 二叉树中序遍历队列递归栈层次遍历二叉搜索树完全二叉树

2021-07-12

2 1114

题解 | #把二叉树打印成多行#

解法一：递归递归方法通过定义递归函数helper，遍历树的每一层，并将结果放入结果数组res的相应位置，因此需要定义level变量以记录当前访问到的层数。在完成对某一凑层的遍历时，按照相同方式递归地访问左孩子和右孩子，且层数加1。实现代码如下： /* struct TreeNode { ...

C++ 二叉树队列递归层次遍历

2021-07-08

4 700

题解 | #对称的二叉树#

解法一：递归方法据题意，对称二叉树定义为：「若一棵二叉树与其镜像二叉树是相同的，则其是对称的二叉树」。因此，判断一棵二叉树是否是对称的，需要从根结点开始，不断地比较左右子树的对称情况，过程如图所示。从根结点（结点）0开始，判断其左右子树是否对称，即判断「结点1所在子树」和「结点2所在子树」是否...

C++ 二叉树队列递归

2021-07-08

3 912