3.1.9 判断平衡二叉树
【考点映射】
- 树
- 二叉树
【出现频度】★★★☆
【难度】★★☆
【题目描述】
给定一个二叉树，判断它是否是高度平衡的二叉树。一棵高度平衡二叉树定义为：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
【参考答案】
平衡二叉树的定义：二叉树的每个节点的左右子树的高度差的绝对值不超过 1，则二叉树是平衡二叉树。平衡二叉树还有一个规律，其所有子数都必须是平衡二叉树，所以我们可以采用递归的方式去判断是否是平衡二叉树。
递归的方法有两种：自顶向下 和 自底向上。
自顶向下递归：
首先需要定义一个求任意一个节点P高度的函数height，有了这个函数，我们就很方便的判断二叉树是否处于平衡状态。
可以利用二叉树的前序遍历，从根节点开始，分别对左右子数进行递归，判断每个节点的高度差是否大于1。自顶向下遍历的弊端就是，对于同一个节点，height函数可能会重复被调用，所以时间复杂度较高。
代码示例（Java）：
class Solution {
public boolean isBalanced(TreeNode root) {
if (root == null) {
return true;
} else {
return Math.abs(height(root.left) - height(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
}
}
public int height(TreeNode root) {
if (root == null) {
return 0;
} else {
return Math.max(height(root.left), height(root.right)) + 1;
}
}
} 自底向上递归：
如果使用自底向上的做法，则对于每个节点，函数 height 只会被调用一次。
自底向上递归的做法类似于后序遍历，对于当前遍历到的节点，先递归地判断其左右子树是否平衡，再判断以当前节点为根的子树是否平衡。如果一棵子树是平衡的，则返回其高度（高度一定是非负整数），否则返回 -1。如果存在一棵子树不平衡，则整个二叉树一定不平衡。
代码示例（Java）：
class Solution {
public boolean isBalanced(TreeNode root) {
return height(root) >= 0;
}
public int height(TreeNode root) {
if (root == null) {
return 0;
}
int leftHeight = height(root.left);
int rightHeight = height(root.right);
if (leftHeight == -1 || rightHeight == -1 || Math.abs(leftHeight - rightHeight) > 1) {
return -1;
} else {
return Math.max(leftHeight, rightHeight) + 1;
}
}
} 【知识点延伸】
二叉树的遍历：
二叉树的遍历分为三种方式：前序遍历、中序遍历、后序遍历。
这里的前、中、后，都是以父节点的相对位置来说的。
前序遍历：父、左、右
中序遍历：左、父、右
后序遍历：左、右、父
这是什么意思呢？可以看我下面的图解：
我们对其进行前序遍历：
同理可得：
中序遍历，遵循左、父、右原则，最终的顺序为：3、5、2、6、1、4、3。
后序遍历，遵循左、右、父原则，最终的顺序为：3、2、5、1、3、4、6。
3.1.10 二分查找
【考点映射】
- 搜索
- 数组
【出现频度】★★★★☆
【难度】★☆
【题目描述】
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
示例 1:
输入: nums = [-1, 0, 3, 5, 9, 12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
示例 2:
输入: nums = [-1, 0, 3, 5, 9, 12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1
【参考答案】
关于二分查找的算法解释：
前提条件：列表必须是经过排序的。
查找逻辑：（假设列表已经排序，并且元素按从小到大排）
- 如果目标值等于中间元素，则找到目标值。
- 如果目标值较小，继续在左侧搜索。
- 如果目标值较大，则继续在右侧搜索。
代码示例（Python）:
def binary_search(nums, target): left = 0 right = len(nums) - 1 while left <= right: center = left + (right - left) // 2 if nums[center] == target: return center if target < nums[center]: right = center - 1 else: left = center + 1 return -1 if __name__ == '__main__': # 测试代码 nums = [-1, 0, 3, 5, 9, 12] target = 5 idx = binary_search(nums, target) print(idx) # 输出：3
3.1.11 什么是深度优先搜索？什么是广度优先搜索？
【考点映射】
- 搜索
- 树
【出现频度】★★★
【难度】★★★
【参考答案】
深度优先搜索属于图算法的一种，是一个针对图和树的遍历算法，英文缩写为DFS，即Depth First Search。一般用于解决走迷宫问题、最大路径问题。
其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次。
深度优先的基本原则：按照某种条件往前试探搜索，如果前进中遭到失败（正如老鼠遇到死胡同）则退回头另选通路继续搜索，直到找到满足条件的目标为止。
例如以A为起点，G为目标开始查找，查找的顺序是：A -> B -> E -> F -> C -> G
广度优先搜索，英文缩写为BFS，即Breadth First Search。属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。
和深度优先算法不同的是，广度优先算法是逐层顺序遍历的，讲究的是广度（宽度）。
还是以A为起点，G为目标开始查找，查找的顺序是：A -> B -> C -> D -> E -> F -> G。
3.1.12 请说说常见的排序算法的时间复杂度和空间复杂度
【考点映射】
【出现频度】★★★☆
【难度】★★★☆
【参考答案】
下面做个汇总：
【知识点拓展】
下面是对一些排序算法中的遇到的名词做个解释：
稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
不稳定：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面。
内排序：所有排序操作都在内存中完成。
外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行。
时间复杂度： 一个算法执行所耗费的时间。
空间复杂度：运行完一个程序所需内存的大小。
O(n+k)：n 个0到k之间的整数的复杂度。
3.1.13 选择排序
【考点映射】
- 排序
【出现频度】★★★☆
【难度】★★
【参考答案】
选择排序(Selection-sort)是一种简单直观的排序算法。其工作原理是：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
动画图解：
代码示例（Python）：
def select_sort(lists): ''' 选择排序（升序）【不稳定排序】 原理： 1、给定一个列表，经过第一轮比较后，找到最小值，与第一个位置交换； 2、接着对不包括第一个元素的剩下的元素，找到最小值，与第二个位置交换； 3、重复该过程，直到进行比较的记录只有一个为止 以 list = [5, 4, 2, 1, 3] 为例： 第一次排序后： [1, 4, 2, 5, 3] 第二次排序后： [1, 2, 4, 5, 3] 第三次排序后： [1, 2, 3, 5, 4] 第四次排序后： [1, 2, 3, 4, 5] 时间复杂度：O(n**2) 空间复杂度：O(1) :param lists: :return: lists ''' count = len(lists) for i in range(0, count): min = i for j in range(i + 1, count): if lists[min] > lists[j]: min = j lists[min], lists[i] = lists[i], lists[min] return lists if __name__ == '__main__': # 测试代码 lst = [5, 4, 3, 2, 1] # 调用冒泡排序 sorted_list = select_sort(lst) print(sorted_list) # 输出：[1, 2, 3, 4, 5]
3.1.14 插入排序
【考点映射】
- 排序
【出现频度】★★★☆
【难度】★★
【参考答案】
插入排序(Insertion Sort)的工作原理是：把n个待排序的元素看成是一个有序表和一个无序表。开始时有序表中只包含1个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，将它插入到有序表中的适当位置，使之成为新的有序表，重复n-1次可完成排序过程。就好像我们在打扑克牌时的洗牌动作。
动画图解：
代码示例（Python）：
def insert_sort(lists): ''' 插入排序（升序）【稳定排序】 原理： 1、假设初始时假设第一个记录，自成一个有序序列，其余的记录为无序序列； 2、从第二个记录开始，按记录大小，依次插入之前的有序序列中； 3、直到最后一个记录插入到有序序列中为止 以 list = [5, 4, 2, 1, 3] 为例： 第一步，插入5之后: [5], 4, 2, 1, 3 第二步，插入4之后: [4, 5], 2, 1, 3 第三步，插入2之后: [2, 4, 5], 1, 3 第四步，插入1之后: [1, 2, 4, 5], 3 第五步，插入3之后: [1, 2, 3, 4, 5] 时间复杂度: O(n) ~ O(n**2) 平均: O(n**2) 空间复杂度: O(1) :param lists: :return: lists ''' count = len(lists) for i in range(1, count): key = lists[i] j = i - 1 while j >= 0: if lists[j] > key: lists[j+1] = lists[j] lists[j] = key j -= 1 return lists if __name__ == '__main__': # 测试代码 lst = [5, 4, 3, 2, 1] # 调用冒泡排序 sorted_list = insert_sort(lst) print(sorted_list) # 输出：[1, 2, 3, 4, 5]
3.1.15 冒泡排序
【考点映射】
- 排序
- 双指针迭代
【出现频度】★★★★☆
【难度】★★
【参考答案】
冒泡排序(Bubbling Sort)是一种简单的排序算法。它的基本思想是：遍历若干次要排序的数列，每次遍历时，都会从前往后依次比较相邻两个数的大小；如果前者比后者大，则交换它们的位置。这样，一次遍历之后，最大的元素就在数列的末尾 采用相同的方法再次遍历时，第二大的元素就被排列在最大元素之前。重复此操作，直到整个数列都有序为止。就好比气泡从水底逐步冒到水面的过程，所以被称为冒泡排序。
动画图解：
京公网安备 11010502036488号