如何通过面试原题、图文详解、实例代码构建二叉搜索树、双指针、贪心面试题汇总？

本文将覆盖 「字符串处理」 + 「动态规划」 方面的面试算法题，文中我将给出： 面试中的题目 解题的思路 特定问题的技巧和注意事项 考察的知识点及其概念 详细的代码和解析 开始之前，我们先看下会有哪些重点案例： 为了方便大家跟进学习，我在 GitHub 建立了一个仓库 仓库地址：超级干货！精心归纳视频、归类、总结，各位路过的老铁支持一下！给个 Star ！ 现在就让我们开始吧！ 二叉搜索树 二叉搜索树（Binary Search Tree），它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉搜索树。 验证二叉搜索树 给定一个二叉树，判断其是否是一个有效的二叉搜索树。 假设一个二叉搜索树具有如下特征： 节点的左子树只包含小于当前节点的数。 节点的右子树只包含大于当前节点的数。 所有左子树和右子树自身必须也是二叉搜索树。 示例 : 输入: 5 / \ 1 4 / \ 3 6 输出: false 解释: 输入为: [5,1,4,null,null,3,6]。 根节点的值为 5 ，但是其右子节点值为 4 。 解题思路 乍一看，这是一道很简单的题。只需要遍历整棵树，检查 node.right.val > node.val 和 node.left.val < node.val 对每个结点是否成立。 问题是，这种方法并不总是正确。不仅右子结点要大于该节点，整个右子树的元素都应该大于该节点。例如:这意味着我们需要在遍历树的同时保留结点的上界与下界，在比较时不仅比较子结点的值，也要与上下界比较。 上述思路可以用递归法实现: 首先将结点的值与上界和下界（如果有）比较。然后，对左子树和右子树递归进行该过程。 视频 视频讲解和源码-验证二叉搜索树 public boolean isValidBST(TreeNode root) { return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE); } private boolean isValidBST(TreeNode root, long min, long max){ if (root == null) { return true; } if (root.val <= min || root.val >= max){ return false; } return isValidBST(root.left, min, root.val) && isValidBST(root.right, root.val, max); } 二叉搜索树中第K小的元素 给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。 说明： 你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。 示例 : 输入: root = [5,3,6,2,4,null,null,1], k = 3 5 / \ 3 6 / \ 2 4 / 1 输出: 3 解题思路 增加 getCount 方法来获取传入节点的子节点数（包括自己） 从 root 节点开始判断k值和子节点数的大小决定递归路径是往左还是往右。