- 正确答案：判断一棵二叉树是否为二叉搜索树（BST），核心是验证其**中序遍历序列严格递增**，或等价地，对每个节点递归验证其值是否落在合法区间（min_val, max_val）内。推荐使用**中序遍历迭代/递归记录前驱值法**（空间O(1)额外变量，时间O(n)），或**带边界范围的递归法**（更直观体现BST定义）。两者均需处理整型边界溢出问题（如节点值为INT_MIN/INT_MAX时）。 - 解答思路： BST的定义是——对任意节点，其左子树所有节点值 < 当前节点值 < 右子树所有节点值（注意：是“所有”，而非仅左右孩子）。因此不能只比较父子关系（如只检查 root->left->val < root->val && root->right->val > root->val），该做法会漏判如[5,3,8,1,6,7,9]中6在5右子树但6>5却违反左子树全部小于根的性质。正确路径有二：（1）中序遍历法：BST的中序遍历结果必为严格升序数组。可边遍历边与前一个访问值比较，一旦发现当前值 <= 前驱值即返回false。用一个指针（如prev）记录上一节点，避免开数组节省空间。（2）区间约束递归法：从根开始，初始合法区间为（-∞, +∞）。访问左子节点时，更新上界为当前节点值；访问右子节点时，更新下界为当前节点值。每到一节点，检查其值是否严格落在当前区间内，否则非法。 - 深度知识讲解：【底层定义本质】BST不是局部性质，而是全局有序性约束。其等价定义有三： (a) 中序遍历序列单调严格递增； (b) 对任意节点x，left_subtree.max < x.val < right_subtree.min； (c) 对任意节点x，x.val严格大于其所有祖先中的“最近右拐祖先”的值（即从根向下路径中，最后一次向右走的父节点值），且严格小于所有“最近左拐祖先”的值。这引出了Morris遍历优化和线索二叉树应用。【实现细节陷阱】 • 整数溢出：若用LONG_MIN/LONG_MAX作边界，需确保节点值类型为int，否则需模板化或用nullptr表示无穷。C++中可用optional，Java可用BigInteger或Long.MIN_VALUE-1L（但不安全），更健壮做法是用指针（如TreeNode* min_node）表示无下界/上界。 • 空树判定：空树是BST（数学归纳基础情形）。 • 相等值处理：BST不允许重复值（经典定义），故必须用“<”和“>”，不能含“<=”或“>=”。若题目允许重复（如左子树≤根），则需明确说明，此时定义变为“左子树所有值 ≤ 根 ≤ 右子树所有值”，但此时中序遍历非严格递增，而为非降序，且需额外处理等于情况（如允许左子树含等于根的值，则右子树也必须能含等于根的值，但经典BST不允许多重键）。【算法复杂度对比】 • 中序递归法：时间O(n)，空间O(h)，h为树高（递归栈），最坏O(n)（链状树）； • 中序迭代法（显式栈）：时间O(n)，空间O(h)，可控； • Morris中序遍历法：时间O(n)，空间O(1)，通过临时修改树结构（将左子树最右节点指向当前节点）实现，结束后恢复原树，适合嵌入式或内存敏感场景； • 区间递归法：时间O(n)，空间O(h)，逻辑最贴近定义，易于理解和调试。【扩展知识点】 • 如何在BST中找第k小元素？→ 中序遍历计数，或利用每个节点存储子树大小（Order Statistic Tree）实现O(h)查询； • 如何验证BST同时统计非法节点个数？→ 改为返回{is_bst, min_val, max_val, node_count}四元组，自底向上合并； • 如果树被修改过（如交换两个节点），如何恢复？→ 中序遍历得错误序列，找逆序对（最多两处），交换对应值即可（LeetCode 99. Recover Binary Search Tree）。 - 代码示例（C++，推荐区间递归法，安全处理INT边界）： ``` struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode() : val(0), left(nullptr), right(nullptr) {} TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} }; bool isValidBST(TreeNode* root) { return isValidBSTHelper(root, nullptr, nullptr); } bool isValidBSTHelper(TreeNode* node, TreeNode* min_node, TreeNode* max_node) { if (!node) return true; if (min_node && node->val <= min_node->val) return false; if (max_node && node->val >= max_node->val) return false; return isValidBSTHelper(node->left, min_node, node) && isValidBSTHelper(node->right, node, max_node); } ``` 注：此写法用TreeNode*传边界，天然规避整数溢出，且语义清晰——min_node表示当前节点必须大于的“最近左拐祖先”，max_node表示必须小于的“最近右拐祖先”。调用时传入isValidBSTHelper(root, nullptr, nullptr)，初始无约束。 - 补充伪代码（中序前驱比较法，递归版）： ``` prev = null function inorderCheck(node): if node is null: return true if not inorderCheck(node.left): return false if prev is not null and node.val <= prev.val: return false prev = node return inorderCheck(node.right) ```

百度实习 推荐算法 一面面经

全站热榜

创作者周榜

百度实习推荐算法一面面经