牛客786963925号

分类

题解(20)

/ 注册

全部文章（共20篇）

题解 | #平衡二叉树#

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

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

2021-07-12

8 1184

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

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

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

2021-07-12

2 1136

题解 | #删除链表中重复的结点#

解法一：虚拟结点此题要求删除「所有的」重复结点，而存在「原链表头结点出现重复」这种情况。因此，为了实现方便，定义虚拟结点dummy，其next指针指向原头结点。思路如图所示。定义指针p，用以遍历链表；定义指针tail，用以指向当前「无重复链表」表尾；每次p指针向前移动，并比较「当前位置...

C++ 链表双指针

2021-07-11

1 928

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

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

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

2021-07-08

4 700

题解 | #按之字形顺序打印二叉树#

解法一：使用队列据题意，需要按照每一层的方式打印二叉树，因此较为直接的解法为「层次遍历」。二叉树的层次遍历通过队列实现较为方便，步骤如下：初始情况，根结点入队列；定义变量size记录当前队列长度；对于「当前队列」，遍历其所有元素：依次出队列、访问该元素、左右孩子入队列。注意：新入队列的「...

C++ 二叉树队列栈

2021-07-08

29 2436

题解 | #对称的二叉树#

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

C++ 二叉树队列递归

2021-07-08

3 912

题解 | #二叉树的下一个结点#

解法一：暴力解法据题意，「某结点的下一个结点」定义为「中序遍历」后的下一个结点。因此暴力解法的步骤为：根据输入的结点以及next指针，先求得二叉树的根结点root；利用root进行二叉树的中序遍历，并定义数组储存中序遍历的结果；遍历该数组，得到「下一个结点」。注意：二叉树的中序遍历步骤...

C++ 二叉树中序遍历

2021-07-07

8 898

题解 | #扑克牌顺子#

解法一：排序在解决此题目之前，需要明确：在达到何种要求时，会实现「顺子」。显而易见，当所抽取的非零牌存在重复时，不可能有顺子出现；此外，由于0可以代替任意牌，因此能否组成顺子是由「非零牌」决定的。故，此题的本质是要我们寻找非零牌之间是否满足一定的关系。题目说明每次抽取牌的数量为5，因此若非零牌...

C++ 哈希表排序

2021-07-07

0 799

题解 | #两数之和#

解法一：暴力解法暴力解法的思路较为直接，在输入数组中分别对两个下标进行遍历，若满足题目要求，直接返回结果（题目中明确说明假设答案唯一）。注意：第一层循环应从0到n-2位置（n为数组长度），即不需要遍历到数组最后一个元素；第二层循环应将第一层循环变量作为起点，遍历至数组最后一个元素。下标从...

C++ 哈希表

2021-07-07

40 5416

题解 | #矩阵的最小路径和#

解法一：回溯法（暴力解法）回溯法遍历所有可走到的路线，并计算每条路线的结果，将最小的结果返回。回溯方法通常需要两个步骤：1. 更新变量，递归到下一步；2.递归返回时，撤销更新对于此题，在每一次递归过程中，需要将当前位置元素的路径和(代码中curSum变量)加入到结果中，并作为参数传入下一次递归；在...

回溯动态规划 C++

2021-07-07

28 3537