本篇本文主要涵盖了二叉搜索树的几个经典问题，包括判断合法、求范围和、根据前序遍历结果建树以及找到最近祖先。下面将详细分析每个问题的解决思路和代码实现。
1.0 判断合法
1.1 使用遍历方式实现验证二叉搜索树
具体思路是利用中序遍历，如果每个节点的值都比前一个节点的值大，则符合二叉搜索树的要求；如果有任何一个节点的值比前一个节点的值大，则不符合二叉搜索树的要求。代码如下：
boolean isValidBST(TreeNode root) { Stack stack = new Stack<>(); TreeNode pre = null; while (root != null || !stack.isEmpty()) { while (root != null) { stack.push(root); root = root.left; } root = stack.pop(); if (pre != null && root.val <= pre.val) { return false; } pre = root; root = root.right; } return true;} 1.2 使用递归方式实现验证二叉搜索树
具体思路是利用递归遍历二叉树，先对左子树进行操作，如果左子树返回的是true，则继续判断当前节点的值；如果左子树返回的是false，则直接返回false结束。如果当前节点的值小于前一个节点的值，则返回false；如果当前节点的值大于前一个节点的值，则继续判断右子树。当遇到节点为null时，返回true。只有当左右子树都为true时，说明该二叉树是二叉搜索树。代码如下：
boolean isValidBST(TreeNode root) { return isValidBST(root, null, null);}boolean isValidBST(TreeNode root, TreeNode min, TreeNode max) { if (root == null) { return true; } if ((min != null && root.val <= min.val) || (max != null && root.val >= max.val)) { return false; } return isValidBST(root.left, min, root) && isValidBST(root.right, root, max);}2.0 求范围和
2.1 使用非递归实现二叉搜索树的范围和
具体思路是利用中序遍历，在满足节点值大于下界low且小于上界high的节点时，将该节点的值累加到sum中，直到遇到节点值大于上界high时，直接返回sum结果。代码如下：
int rangeSumBST(TreeNode root, int low, int high) { if (root == null) { return 0; } int sum = 0; Stack stack = new Stack<>(); while (root != null || !stack.isEmpty()) { while (root != null) { stack.push(root); root = root.left; } root = stack.pop(); if (root.val > high) { break; } if (root.val >= low) { sum += root.val; } root = root.right; } return sum;} 2.2 使用递归方式实现二叉搜索树的范围和
具体思路是先考虑满足范围low和high的节点值，需要返回当前节点的值加上左子树和右子树中满足范围的节点值。然后考虑不满足范围low和high的节点值，当节点值小于下界low时，不需要递归左子树，只需要递归右子树；当节点值大于上界high时，不需要递归右子树，只需要递归左子树。代码如下：
int rangeSumBST(TreeNode root, int low, int high) { if (root == null) { return 0; } if (root.val < low) { return rangeSumBST(root.right, low, high); } if (root.val > high) { return rangeSumBST(root.left, low, high); } return root.val + rangeSumBST(root.left, low, high) + rangeSumBST(root.right, low, high);}3.0 根据前序遍历结果建树
3.1 使用非递归实现前序遍历构造二叉搜索树
具体思路是利用数组的第一个值作为根节点的值，然后遍历数组从索引1开始到数组长度-1。对于每个数组的值，创建一个新的节点，并使用insert方法将该节点插入二叉搜索树中。
关键是使用非递归的方式实现insert方法。首先定义一个parent变量，用来记录p的父节点。然后循环遍历p，如果p的值大于当前节点的值，先将parent赋值为p，然后将p移动到p的左子节点；如果p的值小于当前节点的值，先将parent赋值为p，然后将p移动到p的右子节点。直到p为null时，跳出循环，此时的parent就是该二叉搜索树的叶子节点。然后根据当前节点的值与parent的值的大小关系，如果当前节点的值大于parent的值，则将parent的右子节点设为当前节点；如果当前节点的值小于parent的值，则将parent的左子节点设为当前节点。代码如下：
TreeNode constructFromPreorder(int[] preorder) { if (preorder == null || preorder.length == 0) { return null; } TreeNode root = new TreeNode(preorder[0]); for (int i = 1; i < preorder.length; i++) { TreeNode node = new TreeNode(preorder[i]); insert(root, node); } return root;}void insert(TreeNode root, TreeNode node) { TreeNode parent = null; TreeNode p = root; while (p != null) { parent = p; if (p.val > node.val) { p = p.left; } else { p = p.right; } } if (parent.val > node.val) { parent.left = node; } else { parent.right = node; }}
3.2 使用递归实现前序遍历构造二叉搜索树
具体思路是递归遍历数组，直到遇到null时，创建一个新的节点。如果节点的值大于当前节点的值，则递归左子树；如果节点的值小于当前节点的值，则递归右子树。每次递归返回时，需要重新链接当前节点的左子树或右子树。代码如下：
TreeNode constructFromPreorder(int[] preorder) { return constructFromPreorder(preorder, 0, preorder.length - 1);}TreeNode constructFromPreorder(int[] preorder, int start, int end) { if (start > end) { return null; } TreeNode root = new TreeNode(preorder[start]); int index = start + 1; while (index <= end && preorder[index] < root.val) { index++; } root.left = constructFromPreorder(preorder, start + 1, index - 1); root.right = constructFromPreorder(preorder, index, end); return root;}4.0 二叉搜索树的最近公共祖先
4.1 使用遍历方式实现二叉搜索树的最近公共祖先
具体思路是从根节点开始遍历二叉搜索树，如果p和q的值都小于当前节点的值，则继续遍历当前节点的左子树；如果p和q的值都大于当前节点的值，则继续遍历当前节点的右子树。如果p和q的值分别位于当前节点的左右子树上，或其中一个节点的值等于当前节点的值，则当前节点就是p和q的最近公共祖先。代码如下：
TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { while (root != null) { if (p.val < root.val && q.val < root.val) { root = root.left; } else if (p.val > root.val && q.val > root.val) { root = root.right; } else { return root; } } return null;}5.0 本篇二叉搜索树实现LeetCode经典题的完整代码
本篇本文的代码实现了以下LeetCode经典题目：
- 判断合法：使用遍历方式实现验证二叉搜索树
- 求范围和：使用非递归实现二叉搜索树的范围和
- 根据前序遍历结果建树：使用非递归实现前序遍历构造二叉搜索树
- 二叉搜索树的最近公共祖先：使用遍历方式实现二叉搜索树的最近公共祖先
以上是本篇本文对二叉搜索树相关问题的详细分析和解决思路。通过对每个问题的具体思路和代码实现的解释，希望能对读者理解和掌握二叉搜索树有所帮助。
