二叉搜索树（BST）：根节点大于等于左子树的所有节点，小于等于右子树的所有节点。故二叉树的中序遍历时有序的！
1.修剪二叉树（669-中）
题目描述：给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。保留在树中的元素的相对结构（即如果没有被移除，原有的父代子代关系都应当保留）。 可证存在唯一的答案。
示例：
image.png
输入：root = [3,0,4,null,2,null,null,1], low = 1, high = 3 输出：[3,2,null,1]
思路：本题使用二叉搜索树的性质进行比较，可以通过递归和迭代两种思路实现。
1.递归实现三部曲：
- 递归函数：返回给定边界的二叉搜索子树。
- 终止条件：节点为null，直接返回
- 递归逻辑：若节点root不在区间内，利用二叉搜索树性质，修剪边界外的节点；否则，递归连接左右子树。
2.迭代实现：
- 通过区间限制，保证当前root节点值在要求范围内
- 根据二叉搜索树的性质依次修剪左右子树。注意：定义cur指针，遍历修剪左右子树。
代码1：递归
public TreeNode trimBST(TreeNode root, int low, int high) { if (root == null) return null; //修剪不满足的点（利用bst树性质） if (root.val > high) return trimBST(root.left, low, high); if (root.val < low) return trimBST(root.right, low, high); //递归的修剪左右子树 root.left = trimBST(root.left, low, high); root.right = trimBST(root.right, low, high); return root; }
代码2：迭代
public TreeNode trimBST(TreeNode root, int low, int high) { if (root == null) return null; //保证根节点在区间范围内 while (root.val > high || root.val < low) { root = root.val > high ? root.left : root.right; } TreeNode cur = root; //修剪左子树（小于low情况） while (cur != null) { while (cur.left != null && cur.left.val < low) { cur.left = cur.left.right; } cur = cur.left; } cur = root; //修剪右子树（大于high情况） while (cur != null) { while (cur.right != null && cur.right.val > high) { cur.right = cur.right.left; } cur = cur.right; } return root; }
2.寻找二叉搜索树的第k个元素（230-中）
题目描述：给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。
示例：
输入：root = [3,1,4,null,2], k = 1 输出：1
思路：本题可以使用迭代遍历和递归进行求解。
1.中序遍历：利用bst树中序升序这一性质，比较容易想到。**设置一个变量进行计数**，当计数达到k，返回结果。 2.递归实现寻找最小k元素：**核心是递归的计算左子树节点数**。递归逻辑：**当左子树节点个数等于k - 1，当前节点即为第k小元素；若个数小于k - 1,结果在左子树，否则在右子树（即寻找第k - (leftCount + 1)）**。注：递归函数的k值不断发生变化。
代码1：中序遍历
public int kthSmallest(TreeNode root, int k) { int count = 0; Stack<TreeNode> stack = new Stack<>(); TreeNode cur = root; while (cur != null || !stack.isEmpty()) { while (cur != null) { stack.push(cur); cur = cur.left; } TreeNode node = stack.pop(); count++; if (count == k) return node.val; cur = node.right; } return -1; }
代码2：递归
public int kthSmallest(TreeNode root, int k) { int leftCount = count(root.left); if (leftCount == k - 1) return root.val; if (leftCount < k - 1) return kthSmallest(root.right, k - leftCount - 1); return kthSmallest(root.left, k); } // 计算二叉树的节点个数 private int count(TreeNode node) { if (node == null) return 0; return count(node.left) + count(node.right) + 1; }
3.把二叉搜索树转化为累加树（538-中）
题目描述：给出二叉搜索树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
示例：
image.png
输入：[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8] 输出：[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]
思路：本题可以使用中序反向遍历进行求解。
1.通过递归，利用BST树中序升序这一性质。基本递归逻辑：累加sum值，并赋值给当前节点。注意：先递归右子树，然后左子树。
2.迭代实现，定义一个cur指针遍历树，使用栈结构压如右子树节点，依次弹出累积sum，并赋值。
代码1：递归
private int sum = 0; public TreeNode convertBST(TreeNode root) { if (root != null) { //递归中序遍历的反序 convertBST(root.right); sum += root.val; root.val = sum; convertBST(root.left); } return root; }
代码2：迭代
public TreeNode convertBST(TreeNode root) { if (root == null) return null; Stack<TreeNode> stack = new Stack<>(); TreeNode cur = root; while (cur != null || !stack.isEmpty()) { while (cur != null) { stack.push(cur); cur = cur.right; } TreeNode node = stack.pop(); sum += node.val; node.val = sum; cur = node.left; } return root; }
4.二叉搜索树的最近公共祖先（235/236-易/中）
题目描述：给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。一个节点也可以是自己的祖先！进阶问题：若二叉树是普通树，那么最近公共祖先怎么求呢？
示例：
image.png
二叉搜索树： 输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8 输出: 6 解释: 节点 2 和节点 8 的最近公共祖先是 6。 二叉树： 输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 输出：3 解释：节点 5 和节点 1 的最近公共祖先是节点 3 。
思路：上述两种情况均可以用递归进行实现。
原问题：基于二叉搜索树性质，也是基本的递归逻辑：若root的值大于p的值且大于q的值，说明最近公共祖先应该在左子树；否则，root的值小于p值并且小于q的值，说明最近公共祖先在右子树。
进阶问题：解法1：递归函数实现：返回以root作为根节点的最近公共祖先；终止条件：root == p || q || null,直接返回root。递归逻辑： 左右子树最近公共祖先都存在，结果只能为root，否则，结果是左右子树其的中一个节点。
解法2：定义一个递归函数：确定最近公共祖先的位置；终止条件：当前节点为空，不是最近公共祖先位置，返回false；递归逻辑：结果为root出现两种可能：1.在左且右子树，2当前节点（自己的祖先），另一个在左右子树
代码1：原问题
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if (root.val > p.val && root.val > q.val) return lowestCommonAncestor(root.left, p, q); if (root.val < p.val && root.val < q.val) return lowestCommonAncestor(root.right, p, q); return root; }
代码2：进阶问题
// 解法1 public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if (root == null || root == p || root == q) return root; TreeNode left = lowestCommonAncestor(root.left, p, q); TreeNode right = lowestCommonAncestor(root.right, p, q); if (left != null && right != null) return root; return left != null ? left : right; } // 解法2 private TreeNode ret = null; public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { dfs(root, p, q); return ret; } private boolean dfs(TreeNode root, TreeNode p, TreeNode q) { if (root == null) return false; //在当前节点 boolean inCurrentNode = root.val == p.val || root.val == q.val; //在左子树 boolean inLeft = dfs(root.left, p, q); //在右子树 boolean inRight = dfs(root.right, p, q); if ((inLeft && inRight) || ((inCurrentNode) && (inLeft || inRight))) { ret = root; } return inLeft || inRight || inCurrentNode; }
5.有序数组转二叉搜索树（108/109-易/难）
题目描述：将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。本题中，一个高度平衡二叉树是指一个二叉树【每个节点】 的左右两个子树的高度差的绝对值不超过 1。
进阶问题：若输入为有序链表，该怎么构建二叉搜索树呢？
示例：
给定有序数组: [-10,-3,0,5,9], 一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树： 0 / \ -3 9 / / -10 5
思路：原问题：本题使用递归进行求解。可以理解为将二叉树的中序遍历（升序）进行复原二叉树，根据升序特性构建二叉搜索树的左右子树，升序的中间元素作为root节点，属于分治的思想。
- 递归函数：根据给定元素构建二叉搜索树
- 终止条件：不满足二叉树（搜索树），即
sIdx > eIdx - 递归逻辑：分治的思想，递归的进行左右子树对应的元素区间。
进阶问题：解法1与原问题类似，解法2：使用占位节点，很巧妙。
法1：与上题思路相同，只不过这里不能像数组那样通过索引寻找中间元素（这里可以参考Leetcode 876寻找链表的中间元素，使用的是快慢指针的思想），递归函数：实现返回链表区间构建的二叉搜索树的root；终止条件：注意当只有一个节点，直接构建node。
法2：由于BST树中序遍历结果刚好是升序链表，我们可以利用这一性质进行优化，即不着急找出中间元素，而是使用一个占位节点，等中序遍历到当前节点进行填充。golbalNode节点负责遍历链表。
代码1：原问题
public TreeNode sortedArrayToBST(int[] nums) { return toBST(nums, 0, nums.length - 1); } private TreeNode toBST(int[] nums, int sIdx, int eIdx){ if (sIdx > eIdx) return null; int mIdx = sIdx + ((eIdx - sIdx) >> 1); //升序数组的中间元素作为root TreeNode root = new TreeNode(nums[mIdx]); //递归的构建root的左右子树 root.left = toBST(nums, sIdx, mIdx - 1); root.right = toBST(nums, mIdx + 1, eIdx); return root; }
代码2：进阶问题
// 解法1：有序链表转二叉搜索树 public TreeNode sortedListToBST(ListNode head) { if (head == null) return null; if (head.next == null) return new TreeNode(head.val); // 递归逻辑 ListNode preMid = preMiddle(head); ListNode mid = preMid.next; preMid.next = null; TreeNode root = new TreeNode(mid.val); root.left = sortedListToBST(head); root.right = sortedListToBST(mid.next); return root; } // 记录中间元素的前一个元素（左边） private ListNode preMiddle(ListNode head) { ListNode fast = head, slow = head, pre = null; while (fast != null && fast.next != null) { pre = slow; slow = slow.next; fast = fast.next.next; } return pre; } // 解法2：中序遍历优化 ListNode globalHead; public TreeNode sortedListToBST(ListNode head) { globalHead = head; ListNode cur = head; int len = 0; while (cur != null) { ++len; cur = cur.next; } return buildTree(0, len - 1); } // 根据链表元素建立树 private TreeNode buildTree(int l, int r) { if (l > r) return null; int mid = l + ((r - l) >> 1); TreeNode root = new TreeNode(); // 占位节点 root.left = buildTree(l, mid - 1); root.val = globalHead.val; // 占位节点赋值 globalHead = globalHead.next; root.right = buildTree(mid + 1, r); return root; }
6.二叉搜索树中寻找两个值，使和等于给定值（653-easy）
题目描述：给定一个二叉搜索树和一个目标结果，如果 BST 中存在两个元素且它们的和等于给定的目标结果，则返回 true。
示例：
输入: 5 / \ 3 6 / \ \ 2 4 7 Target = 9 输出: True
思路：注意：本题不能使用递归的寻找左右子树的分治思想，因为两个数可能分别在左右两个子树。
法1：可以使用双指针遍历BST树中序遍历的结果（中序升序简化查找），容易理解，实现简单。
法2：使用hashset存储已经遍历的值，再判断集合中有无k - root.val，即递归逻辑。递归函数：当前树有没有目标节点。
代码1：中序遍历+双指针
private List<Integer> ret = new ArrayList<>(); // 双指针判断是否存在 public boolean findTarget(TreeNode root, int k) { inOrder(root); int l = 0, r = ret.size() - 1; while (l < r) { int sum = ret.get(l) + ret.get(r); if (sum > k) r--; else if (sum < k) l++; else return true; } return false; } // 中序遍历二叉搜索树并存储 private void inOrder(TreeNode root) { if (root == null) return; inOrder(root.left); ret.add(root.val); inOrder(root.right); }
代码2：hashset遍历
private Set<Integer> set = new HashSet<>(); public boolean findTarget(TreeNode root, int k) { if (root == null) return false; // 找到值，返回true if (set.contains(k - root.val)) return true; set.add(root.val); // 递归左右子树 return findTarget(root.left, k) || findTarget(root.right, k); }
