在牛客刷二叉树题单的时候BM34这道题几乎都会被推荐到。题目描述不长给定一棵二叉树的根节点判断它是不是二叉搜索树并且专门强调左子树上的所有节点均严格小于当前节点、右子树上的所有节点均严格大于当前节点。乍一看这就是概念题但真正动手写代码后很多人都在这道题上卡过几次尤其是只把定义记了个大概就急着写递归的人。这篇文章我会把判断二叉搜索树这件事彻底讲透先拆穿一个非常隐蔽的误区再给出中序遍历判增法和区间收敛法两种主流解法最后结合牛客BM34的判题环境把空节点、重复值、极端数值这些容易被忽略的细节全部摆出来。无论你是准备笔试的应届生还是复习算法面试的研发岗都能直接抄代码也能讲明白原理。先给结论判断BST有三个可靠方向——中序遍历判严格递增、区间边界的递归收敛、以及对应的迭代写法。下面逐个拆开。1. 先拆穿一个常见误区局部大小对不代表全局是BST1.1 一个能骗过全部局部检查的反例很多人第一次写这道题代码是这样的检查当前节点是否大于左孩子、小于右孩子然后递归检查左右子树。这个写法在绝大多数例子上都能过但遇到下面这棵树就会翻车5 / \ 3 7 / \ 2 6按每个节点大于左孩子且小于右孩子来检查节点5左孩子3小于5右孩子7大于5通过节点3左孩子2小于3右孩子6大于3通过节点7没有左孩子右子树为空通过节点2、6叶子节点不用比较通过。每个节点的局部关系都成立但这棵树不是二叉搜索树。为什么因为6在5的右子树里作为右子树上的节点它必须严格大于根节点5而实际6大于3却小于5它越过了根节点的约束。判断BST看的是子树上的所有节点不是直接孩子节点。1.2 为什么每个节点和孩子比一比会漏局部检查的问题在于它只约束了相邻两层的关系。拿上面这棵树来说节点6挂在3的右子树上它只要大于3就通过了3这层检查节点7只要大于5也通过了。但6和5之间隔着33的检查根本管不到6的边界。你可以把树的约束理解成门禁权限每个楼层保安只能验证自己这一层的出入证但全楼的门禁规则是总部统一下发的。你只让每个保安凭感觉放行自然可能混进拿着错误权限的人。BST定义里的所有节点这四个字就是在要求每一层的门禁都要对齐总部的统一规则。1.3 把定义翻译成可执行的条件既然局部比较不够那怎么把左子树所有节点严格小于当前节点、右子树所有节点严格大于当前节点翻译成代码逻辑核心思路是让边界在递归时不断传递从根节点出发整棵树没有任何上下界约束。往左子树走的时候根节点的值就变成左子树上所有节点的上限——左子树里任何一个节点都不得超过这个值往右子树走的时候根节点的值变成下限——右子树里任何一个节点都不得小于这个值。每深入一层边界就多收一圈任何越过祖先边界的节点都会立刻暴露。这个思路对应两种经典实现一种是利用BST中序遍历严格递增的性质另一种是直接在递归函数里维护上下界参数。下面两章分别展开。2. 中序遍历判增法最直觉的解法却有四个细节2.1 先证明一个充要条件二叉搜索树有一个非常重要的性质中序遍历结果是严格递增的。为什么中序遍历的顺序是左子树、根节点、右子树。BST保证了左子树上所有节点严格小于根节点右子树上所有节点严格大于根节点所以输出序列必然是左子树的小值们 → 更小的根值不对左子树都比根小所以整个序列从小到大排下来。反过来也成立如果一棵二叉树的中序遍历严格递增那么这棵树一定是BST。原因在于中序序列中任何一个节点它左子树的所有节点都排在它前面、值都更小右子树的所有节点都排在它后面、值都更大这就和BST的定义完全吻合。所以中序严格递增与是二叉搜索树互为充要条件。基于这个等价关系最直白的解法就是中序遍历途中检查相邻两个节点是否严格递增。2.2 标准递归实现推荐指针版前驱中序遍历的递归写法很简单关键是上一个被访问的节点怎么保存。这里我推荐用TreeNode* pre而不是一个整数原因后面马上说。class Solution { public: bool isValidBST(TreeNode* root) { pre nullptr; // 入口处必须重置 return inorder(root); } private: TreeNode* pre; // 记录中序遍历的前一个节点 bool inorder(TreeNode* root) { if (!root) return true; if (!inorder(root-left)) return false; if (pre pre-val root-val) return false; pre root; return inorder(root-right); } };核心只有三行先递归左子树然后把当前节点和前驱节点比较再递归右子树。如果中序序列里出现了pre-val root-val说明不是严格递增直接返回false。2.3 细节一严格递增里相等也算失败题目明确说的是严格小于严格大于所以节点值相等的情况不满足BST定义。比如[2,2]这棵树根是2左孩子也是2左子树上所有节点必须严格小于根但2等于2不合格。代码里必须写成pre-val root-val返回false不能写成。这个是很多初学者最容易写错的地方尤其在重复值出现时写错一个符号就是零分和满分的区别。2.4 细节二初始边界值不能想当然如果你用long long pre LLONG_MIN来做第一节点比较理论上没问题因为节点值一般都在int范围内。但如果你遇到某个节点值正好等于LLONG_MIN的极端构造第一轮比较pre root-val就会误判。更稳妥的做法是像我上面那样用空指针作为前驱不存在的标记。第一次访问时pre是nullptr跳过比较之后每访问一个节点都重新赋值。这样完全没有边界值风险。2.5 细节三递归深了会爆栈迭代版怎么改当二叉树退化成链表形态比如每个节点只有右孩子递归深度可能达到10万以上很多判题平台的系统栈会撑不住。这时候建议改成迭代中序用显式栈代替系统递归。class Solution { public: bool isValidBST(TreeNode* root) { stackTreeNode* st; TreeNode* cur root; TreeNode* pre nullptr; while (cur || !st.empty()) { while (cur) { st.push(cur); cur cur-left; } cur st.top(); st.pop(); if (pre pre-val cur-val) return false; pre cur; cur cur-right; } return true; } };这个写法和递归版逻辑完全一致先一路压左孩子到底再弹出一个节点当作根访问检查完顺手把指针切到右子树。空间复杂度还是O(h)但不再消耗系统栈。2.6 细节四递归入口必须重置前驱状态如果pre是类的成员变量而判题系统多次复用同一个类实例——牛客和LeetCode都会出现这种情况——上一次调用留下的pre值会污染下一次判断。所以在isValidBST入口处第一行就要写pre nullptr;这是基本功。3. 区间收敛法把所有节点翻译成不断收紧的上下界3.1 两个边界参数是怎么长出来的中序遍历法虽然好写但要证明中序递增却一定有BST稍微绕一点。如果你面试时想讲得更直观区间收敛法更合适。它的思路完全照搬定义递归过程中维护一个开区间(low, high)当前节点的值必须落在区间内。初始区间是负无穷到正无穷。每次往左子树递归时上界high更新为当前节点的值因为左子树所有节点必须小于它每次往右子树递归时下界low更新为当前节点的值因为右子树所有节点必须大于它。这样每个节点不仅受到父节点约束还受到所有祖先节点形成的边界约束。第一章里那个6越过5的反例在区间法下就会在进入15的左子树时以10作为下界、15作为上界6落在这个区间之外立即返回false。3.2 递归代码与一个关键推演直接看代码class Solution { public: bool isValidBST(TreeNode* root) { return check(root, LLONG_MIN, LLONG_MAX); } private: bool check(TreeNode* root, long long low, long long high) { if (!root) return true; if (root-val low || root-val high) return false; return check(root-left, low, root-val) check(root-right, root-val, high); } };注意边界是开区间所以判断条件用和。也就是说节点值恰好等于边界值也算越界。拿一个经典的错误用例推演树[10,5,15,null,null,6,20]。根节点10区间(LLONG_MIN, LLONG_MAX)通过左子树5区间(LLONG_MIN, 10)5在区间内通过右子树15区间(10, LLONG_MAX)15在区间内通过15的左子树6区间(10, 15)6小于下界10返回false。递归走到这里就停了。整棵树不是BST因为6虽然在15的左子树里却比祖先根节点10更小。区间法直接在参数传递时把这个矛盾暴露出来。3.3 用节点指针代替数字边界绕开所有边界值问题long long版本有个潜在适用性问题如果题目节点的值超过long long范围这个写法就撑不住了。虽然一般题目不会这么变态但更优雅的解法是用节点指针来做边界。左边界指针表示当前节点必须严格大于这个指针指向的值右边界指针表示当前节点必须严格小于这个指针指向的值。边界值就是指针所指节点的val不存在任何数字范围限制。class Solution { public: bool isValidBST(TreeNode* root) { return check(root, nullptr, nullptr); } private: bool check(TreeNode* root, TreeNode* lowNode, TreeNode* highNode) { if (!root) return true; if (lowNode root-val lowNode-val) return false; if (highNode root-val highNode-val) return false; return check(root-left, lowNode, root) check(root-right, root, highNode); } };你会发现指针版比数字版更好理解往左走时把当前节点root传给右边界参数highNode往右走时把当前节点传给左边界参数lowNode。它完全用节点本身充当哨兵代码里传递的就是你被谁管着的信息。3.4 为什么我更愿意用区间法给面试官讲题中序法我一般作为第二解法区间法作为主推。原因有两点一是解释成本低。给面试官讲中序法你得先讲中序遍历顺序再证明严格递增的充要性中间还要说清楚为什么递增一段就能代表整棵树。区间法则一句话就能讲完每个节点都必须落在祖先围成的范围内不满足就不是BST直接对应题目给的定义。二是排查错误更直观。中序法出问题时你还要回头去打印序列看哪里递增被打断区间法出问题时边界参数一般是显式的能直接看出是哪一层边界收得不对。4. 牛客BM34 的输入、空节点与重复值究竟有多少坑4.1 函数签名与TreeNode结构在牛客BM34里题目给你的是已经构造好的二叉树根节点函数签名长这样bool isValidBST(TreeNode* root);TreeNode的结构是struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} };也就是说你不需要自己解析输入字符串平台内部会先把层序序列建成树再调用你的方法。本地调试时则需要自己构造这棵树。4.2 层序输入里#空节点是怎么回事牛客二叉树的输入描述通常是层序序列比如{1,2,3,#,#,4,5}。这里#代表空节点不是字符串而是二叉树里的这个位置没有节点。如果你想在本地复现这道题需要自己写一个从层序序列建树的函数。参考实现用队列按层扩展TreeNode* buildTree(const vectorstring nodes) { if (nodes.empty() || nodes[0] #) return nullptr; TreeNode* root new TreeNode(stoi(nodes[0])); queueTreeNode* q; q.push(root); int idx 1; while (!q.empty() idx nodes.size()) { TreeNode* cur q.front(); q.pop(); if (idx nodes.size() nodes[idx] ! #) { cur-left new TreeNode(stoi(nodes[idx])); q.push(cur-left); } idx; if (idx nodes.size() nodes[idx] ! #) { cur-right new TreeNode(stoi(nodes[idx])); q.push(cur-right); } idx; } return root; }这里每次弹出一个父节点就尝试读两个子节点遇到#就跳过。层序建树的核心原理是父节点出队顺序正好和子节点入队顺序一致所以用一个先进先出队列就能保证按层构建。4.3 判题用例一定会用到的边界场景牛客这类平台的测试用例设计得很刁钻我总结几个几乎必考的场景空树{}这种树是不是BST牛客的约定是返回true只有根节点{1}返回true包含INT_MIN或INT_MAX的节点如果你中序法的初始边界是INT_MIN遇到根节点正好是INT_MIN的用例就直接误判重复值{1,1}、{2,2,1}这类输入因为BST要求严格不等所以全部返回false深层右子树的左孙越界比如{10,5,15,#,#,6,20}最经典的翻车树。4.4 可直接提交的完整代码结合前面的分析我推荐在BM34直接提交区间指针版代码短且没有边界值隐患class Solution { public: bool isValidBST(TreeNode* root) { return check(root, nullptr, nullptr); } private: bool check(TreeNode* root, TreeNode* lowNode, TreeNode* highNode) { if (!root) return true; if (lowNode root-val lowNode-val) return false; if (highNode root-val highNode-val) return false; return check(root-left, lowNode, root) check(root-right, root, highNode); } };如果你用Python代码更短而且None天然就是无边界的标记class Solution: def isValidBST(self, root: TreeNode) - bool: def check(node, low, high): if not node: return True if low is not None and node.val low: return False if high is not None and node.val high: return False return check(node.left, low, node.val) and check(node.right, node.val, high) return check(root, None, None)注意Python里判断写的是 low和 high和C完全一致都是开区间语义。5. 三种解法实测对比和一些调试心得5.1 时间复杂度、空间复杂度、代码量对比三种解法时间上没有任何区别都是O(n)每个节点访问一次。空间上递归写法都是O(h)h是树高中序迭代用显式栈也是O(h)。真正的差异在代码量、可解释性和边界处理上。解法时间复杂度空间复杂度代码量边界风险推荐场景中序递归O(n)O(h)最短前驱状态需重置面试时快速写出验证方案中序迭代O(n)O(h)稍长栈操作易写错笔试防爆栈区间递归O(n)O(h)中等几乎无边界风险讲原理、正式提交5.2 建议自测的六组用例无论你最终选哪种解法本地调试时建议把下面这组用例全部跑一遍输入层序预期结果验证点{2,1,3}true标准BST{1,2,3}false根1左子2违反左小右大{5,4,6,#,#,3,7}false6的左子树出现3越过根5{10,5,15,#,#,6,20}false15的左子树出现6小于根10{}true空树约定为true{1,1}false重复值不满足严格不等第三、第四条就是专门用来杀局部比较法的。如果这些用例全过你的解法基本稳了。5.3 我在这道题上翻过的车我第一次写的版本就是局部比较法在{5,4,6,#,#,3,7}这个用例上当场被教育。那之后我改用中序遍历又踩了第二个坑pre初始值用了INT_MIN遇到一个节点值恰好是INT_MIN的用例第一轮比较就误判。后来我把pre改成TreeNode*彻底解决了边界值问题。再后来写区间法时又悟到这类全局约束问题最不容易出错的思路就是把约束变成递归参数显式传递。这个经验后来帮了我很多忙——判断平衡二叉树、验证合法路径、检查二叉搜索树的子树本质都是同一类问题。5.4 一个小习惯先打印中序序列再断言如果你不幸在牛客上反复提交不通过我建议本地先写个小函数打印中序序列人工看一眼是不是严格递增。比如{5,4,6,#,#,3,7}的中序结果是[4,5,3,6,7]你一眼就能看出3的位置不对比在递归里打断点快得多。这个习惯我一直用到现在排查所有二叉树遍历类问题都好使。打印结果永远是最直观的调试手段别一上来就盯着代码看逻辑。