type
status
password
date
slug
summary
category
URL
tags
icon
定义
二叉搜索树（BST）是二叉树的一种特殊表示形式，它满足如下特性：
- 每个节点中的值必须大于（或等于）存储在其左侧子树中的任何值。
- 每个节点中的值必须小于（或等于）存储在其右子树中的任何值。
我们可以按照前序、中序和后序来遍历一个二叉搜索树。 但是值得注意的是，对于二叉搜索树，我们可以通过
中序遍历得到一个递增的有序序列。
98. 验证二叉搜索树
首先进行中序遍历，然后判断中序遍历的结果是不是递增序列
173. 二叉搜索树迭代器
700. 二叉搜索树中的搜索
给定二叉搜索树（BST）的根节点 root 和一个整数值 val。你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 null 。
701. 二叉搜索树中的插入操作
给定二叉搜索树（BST）的根节点 root 和要插入树中的值 value ，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ，新值和原始二叉搜索树中的任意节点值都不同。
450. 删除二叉搜索树中的节点(最难)
给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
题解
- root 为叶子节点，没有子树。此时可以直接将它删除，即返回空。
- root 只有左子树，没有右子树。此时可以将它的左子树作为新的子树，返回它的左子节点。
- root 只有右子树，没有左子树。此时可以将它的右子树作为新的子树，返回它的右子节点。
- root 有左右子树，这时可以将 root 的右子树作为新的根节点代替root；将root的左子树作为 root 的右子树中最小结点的左子树。