[TOC] ## 定义 * 每个节点中的值必须大于（或等于）存储在其左子树中的任何值 * 每个节点中的值必须小于（或等于）存储在其右子树中的任何值 ## 应用 #### [98\. 验证二叉搜索树](https://leetcode-cn.com/problems/validate-binary-search-tree/) 验证二叉搜索树 ```cpp class Solution { public: bool isValidBST(TreeNode* root) { TreeNode* prev = NULL; return helper(root, prev); } bool helper(TreeNode* root, TreeNode*& prev) { if (root == NULL) return true; if (!helper(root->left, prev)) return false; if (prev && prev->val >= root->val) return false; prev = root; return helper(root->right, prev); } }; ``` #### [701\. 二叉搜索树中的插入操作](https://leetcode-cn.com/problems/insert-into-a-binary-search-tree/) 给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 保证原始二叉搜索树中不存在新值。 注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回任意有效的结果。 ```cpp class Solution { public: TreeNode* insertIntoBST(TreeNode* root, int val) { if (root == NULL) return new TreeNode(val); if (val < root->val) root->left = insertIntoBST(root->left, val); else root->right = insertIntoBST(root->right, val); return root; } }; ``` #### [450\. 删除二叉搜索树中的节点](https://leetcode-cn.com/problems/delete-node-in-a-bst/) 给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。 一般来说，删除节点可分为两个步骤： 1. 首先找到需要删除的节点； 2. 如果找到了，删除它。 ``` class Solution { public: TreeNode* deleteNode(TreeNode* root, int key) { if (root == NULL) return root; if (key < root->val) root->left = deleteNode(root->left, key); else if (key > root->val) root->right = deleteNode(root->right, key); else { TreeNode* del = root; if (root->left == NULL) root = root->right; else if (root->right == NULL) root = root->left; else { TreeNode* successor = new TreeNode(minimum(root->right)->val); root->right = deleteNode(root->right, successor->val); successor->left = root->left; successor->right = root->right; root = successor; } delete del; } return root; } TreeNode* minimum(TreeNode* root) { while (root->left) root = root->left; return root; } }; ``` #### [110\. 平衡二叉树](https://leetcode-cn.com/problems/balanced-binary-tree/) 给定一个二叉树，判断它是否是高度平衡的二叉树。 本题中，一棵高度平衡二叉树定义为： 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。 ``` class Solution { public: bool isBalanced(TreeNode* root) { if (root == NULL) return true; if (abs(height(root->left) - height(root->right)) > 1) return false; return isBalanced(root->left) && isBalanced(root->right); } int height(TreeNode* root) { if (root == NULL) return 0; int leftHeight = height(root->left); int rightHeight = height(root->right); return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1; } }; ``` #### [剑指 Offer 68 - I. 二叉搜索树的最近公共祖先](https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-zui-jin-gong-gong-zu-xian-lcof/) 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。 ```cpp class Solution { public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if (root == NULL) return root; if (min(p->val, q->val) <= root->val && max(p->val, q->val) >= root->val) return root; if (min(p->val, q->val) > root->val) return lowestCommonAncestor(root->right, p, q); return lowestCommonAncestor(root->left, p, q); } }; ``` ### [剑指 Offer 33. 二叉搜索树的后序遍历序列](https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/5vwxx5/) 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 `true`，否则返回 `false`。假设输入的数组的任意两个数字都互不相同。 ```cpp class Solution { public: bool verifyPostorder(vector<int>& postorder) { return helper(postorder, 0, postorder.size() - 1); } bool helper(vector<int>& postorder, int i, int j) { if (i >= j) return true; int k = i; while (postorder[k] < postorder[j]) k++; int m = k; while (postorder[k] > postorder[j]) k++; return k == j && helper(postorder, i, m - 1) && helper(postorder, m, j - 1); } }; ```