废话不多说，喊一句号子鼓励自己：程序员永不失业，程序员走向架构！本篇Blog的主题是【】，使用【】这个基本的数据结构来实现，这个高频题的站点是：CodeTop，筛选条件为：目标公司+最近一年+出现频率排序，由高到低的去牛客TOP101去找，只有两个地方都出现过才做这道题（CodeTop本身汇聚了LeetCode的来源），确保刷的题都是高频要面试考的题。
明确目标题后，附上题目链接，后期可以依据解题思路反复快速练习，题目按照题干的基本数据结构分类，且每个分类的第一篇必定是对基础数据结构的介绍。
验证二叉搜索树【MID】
中序遍历递归验证二叉搜索树
题干
解题思路
二叉搜索树的特性就是中序遍历是递增序,既然是判断是否是二叉搜索树，那我们可以使用中序递归遍历。只要之前的节点是二叉树搜索树，那么如果当前的节点小于上一个节点值那么就可以向下判断
代码实现
给出代码实现基本档案
基本数据结构：二叉树
辅助数据结构：无
算法：递归，DFS
技巧：无
其中数据结构、算法和技巧分别来自：
- 10 个数据结构：数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树
- 10 个算法：递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法
- 技巧：双指针、滑动窗口、中心扩散
当然包括但不限于以上
import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * public TreeNode(int val) { * this.val = val; * } * } */ public class Solution { private int maxValue = Integer.MIN_VALUE; /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param root TreeNode类 * @return bool布尔型 */ public boolean isValidBST (TreeNode root) { if (root == null) { return false; } return dfsCheck(root); } private boolean dfsCheck(TreeNode root) { // 1 判断的递归终止条件,到达叶子节点 if (root == null) { return true; } // 2 如果左子树不满足条件，返回false if (!dfsCheck(root.left)) { return false; } // 如果当前值小于历史最大值，则不满足，返回false if (root.val < maxValue) { return false; } // 更新历史最大值为当前值 maxValue = root.val; // 3 返回右子树的结果 return dfsCheck(root.right); } }
复杂度分析
时间复杂度：O(n)，其中n为二叉树的节点数，遍历整棵二叉树
空间复杂度：O(n)，最坏情况下，二叉树化为链表，递归栈深度最大为n
将二叉搜索树转为排序的双向循环链表【MID】
数据结构考察，二叉搜索树和双向链表互转
题干
解题思路
本文解法基于性质：二叉搜索树的中序遍历为递增序列 。 将 二叉搜索树 转换成一个 “排序的循环双向链表” ，其中包含三个要素：
- 排序链表： 节点应从小到大排序，因此应使用 中序遍历 “从小到大”访问树的节点。
- 双向链表： 在构建相邻节点的引用关系时，设前驱节点 pre 和当前节点 cur ，不仅应构建
pre.right = cur，也应构建cur.left = pre。 - 循环链表： 设链表头节点 head 和尾节点 tail ，则应构建 head.left = tail 和 tail.right = head 。
整体如下图所示
中序遍历 为对二叉树作 “左、根、右” 顺序遍历算法流程：dfs(cur): 递归法中序遍历；
- 终止条件： 当节点 cur 为空，代表越过叶节点，直接返回；
- 递归左子树，即 dfs(cur.left) ； 构建链表：当 pre 为空时： 代表正在访问链表头节点，记为 head ；当 pre 不为空时： 修改双向节点引用，
即 pre.right = cur ， cur.left = pre ；保存 cur ： 更新 pre = cur ，即节点 cur 是后继节点的 pre ； - 递归右子树，即 dfs(cur.right) ；处理过程同上
treeToDoublyList(root)：
特例处理： 若节点 root 为空，则直接返回；初始化： 空节点 pre ；转化为双向链表： 调用 dfs(root) ；构建循环链表： 中序遍历完成后，head 指向头节点， pre 指向尾节点，因此修改 head 和 pre 的双向节点引用即可；返回值： 返回链表的头节点 head 即可；
代码实现
给出代码实现基本档案
基本数据结构：二叉树
辅助数据结构：无
算法：递归，DFS
技巧：无
其中数据结构、算法和技巧分别来自：
- 10 个数据结构：数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树
- 10 个算法：递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法
- 技巧：双指针、滑动窗口、中心扩散
当然包括但不限于以上
/* // Definition for a Node. class Node { public int val; public Node left; public Node right; public Node() {} public Node(int _val) { val = _val; } public Node(int _val,Node _left,Node _right) { val = _val; left = _left; right = _right; } }; */ class Solution { // 1 定义头节点和前置节点 private Node head; private Node pre; public Node treeToDoublyList(Node root) { if (root == null) { return null; } // 1 递归处理节点关系 dfsGen(root); // 2 绑定头尾节点 // 初始化头尾节点相互指向:尾节点的下一个是头节点 pre.right = head; // 初始化头尾节点相互指向:头节点的上一个是尾节点 head.left = pre; // 3 返回头节点 return head; } private void dfsGen(Node cur) { if (cur == null) { return; } // 1 中序遍历，先处理左子树 dfsGen(cur.left); if (pre == null) { // 记录头节点位置 head = cur; } else { // 本级任务:pre节点与cur节点进行绑定 pre.right = cur; cur.left = pre; } pre = cur; // 3 中序遍历，最后处理右子树 dfsGen(cur.right); } }
复杂度分析
时间复杂度：O(n)，其中n为二叉树的节点数，遍历整棵二叉树
空间复杂度：O(n)，最坏情况下，二叉树化为链表，递归栈深度最大为n
拓展知识：二叉搜索树
二叉搜索树（Binary Search Tree，简称BST）是一种二叉树的形式，它具有一些特殊的性质，使得它在存储和检索数据方面非常高效。BST中的每个节点都包含一个值，而且对于每个节点，其左子树中的所有节点的值都小于该节点的值，而右子树中的所有节点的值都大于该节点的值。这个性质使得在BST中查找、插入和删除操作都可以在平均情况下在**O(log n)**的时间内完成，其中n是BST中节点的数量。
以下是一些BST的基本性质和操作：
- 查找：要查找BST中的一个特定值，可以从根节点开始，比较目标值与当前节点的值。如果目标值小于当前节点的值，就在左子树中继续查找；如果大于当前节点的值，就在右子树中查找。如果找到目标值，操作成功；否则，继续向下查找，直到找到目标值或者达到叶子节点。
- 插入：要插入一个新值到BST中，首先执行查找操作，找到插入位置。然后，在插入位置创建一个新节点，将新值赋给该节点，并将其连接到树中的合适位置。插入操作确保BST的性质仍然成立。
- 删除：要删除BST中的一个值，首先执行查找操作，找到要删除的节点。然后，根据节点的子树情况执行不同的操作：如果节点是叶子节点，直接删除它；如果节点有一个子节点，将子节点提升到删除节点的位置；如果节点有两个子节点，可以选择用其前驱节点或后继节点替代，然后递归地删除前驱或后继节点。
BST的性能取决于树的结构，最好的情况是平衡二叉搜索树（Balanced BST），其中左子树和右子树的高度大致相等，这样可以确保查找、插入和删除等操作都能在O(log n)的时间内完成。常见的平衡BST包括AVL树和红黑树。
然而，如果BST不平衡，最坏情况下操作的时间复杂度可能会退化到O(n)，例如当BST退化成一个链表时。因此，在实际应用中，通常需要采取一些方法来维护BST的平衡性，以确保高效的性能。
