98.验证二叉搜索树
给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下:
节点的左子树只包含 小于 当前节点的数。
节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。示例 1：输入：root = [2,1,3] 输出：true
示例 2：输入：root = [5,1,4,null,null,3,6] 输出：false 解释：根节点的值是 5 ，但是右子节点的值是 4 。
分析:
1.BST 的中序遍历是完全有序的, 我们利用这个性质, 采用迭代的方法中序遍历二叉树, 然后发现如果有任何一个元素前一个元素和后一个元素是违反有序关系的, 那么一定非BST
2.迭代中序遍历, 并额外维护一个 preNode 指针, 遍历过程中每次比较 preNode 和 cur 的关系是不满足 < 情况判定非BST
class Solution {
public:
bool isValidBST(TreeNode* root) {
stack<TreeNode*> s;
TreeNode* preNode = nullptr;
while (root != nullptr || !s.empty()) {
while (root != nullptr) {
s.push(root);
root = root->left;
}
root = s.top();
s.pop();
if (preNode != nullptr && preNode->val >= root->val) {
return false;
}
preNode = root;
root = root->right;
}
return true;
}
};
700.二叉搜索树中的搜索
给定二叉搜索树（BST）的根节点 root 和一个整数值 val。
你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 null 。示例 1: 输入：root = [4,2,7,1,3], val = 2 输出：[2,1,3]
示例 2: 输入：root = [4,2,7,1,3], val = 5 输出：[]
分析:
1.直接逐个比较根节点和 val, 如果根节点比 val 小, 那么就是直接递归搜右子树; 否则搜左子树
class Solution {
public:
TreeNode* searchBST(TreeNode* root, int val) {
if (root == nullptr) {
return nullptr;
}
if (root->val == val) {
return root;
}
if (root->val < val) {
return searchBST(root->right, val);
}
if (root->val > val) {
return searchBST(root->left, val);
}
return nullptr;
}
};
701.二叉搜索树中的插入操作
给定二叉搜索树（BST）的根节点 root 和要插入树中的值 value ，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ，新值和原始二叉搜索树中的任意节点值都不同。
注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。示例 1： 输入：root = [4,2,7,1,3], val = 5 输出：[4,2,7,1,3,5] 解释：另一个满足题目要求可以通过的树是：
示例 2： 输入：root = [40,20,60,10,30,50,70], val = 25 输出：[40,20,60,10,30,50,70,null,null,25]
示例 3： 输入：root = [4,2,7,1,3,null,null,null,null,null,null], val = 5 输出：[4,2,7,1,3,5]
分析:
1.插入操作其实就是找正确的插入位置
2.仍然采用二叉树递归的插入
class Solution {
public:
TreeNode* insertIntoBST(TreeNode* root, int val) {
if (root == nullptr) {
return new TreeNode(val);
}
if (root->val < val) {
root->right = insertIntoBST(root->right, val);
}
if (root->val > val) {
root->left = insertIntoBST(root->left, val);
}
return root;
}
};
450.删除二叉搜索树中的节点
给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
一般来说，删除节点可分为两个步骤： 1.首先找到需要删除的节点；2.如果找到了，删除它。示例 1: 输入：root = [5,3,6,2,4,null,7], key = 3 输出：[5,4,6,2,null,null,7]
解释：给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。
一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。
另一个正确答案是 [5,2,6,null,4,null,7]。示例 2: 输入: root = [5,3,6,2,4,null,7], key = 0 输出: [5,3,6,2,4,null,7] 解释: 二叉树不包含值为 0 的节点
示例 3: 输入: root = [], key = 0 输出: []
分析:
1.对原始的根节点来说, 删除的节点有三种情况, 一种是当前根节点, 一种是属于左右子树节点
(i). 如果是根节值小于 key, 那么我们在右子树里面递归删除右子树 (也是BST) 中的节点, 同理如果是根节值小于 key, 那么在左子树里面递归删除左子树 (也是BST) 中的节点; 因此框架上整体采用分解问题的思维
(ii). 如果是根节点, 牵一发而动全身, 需要思考下怎么变
得到整体的处理框架如下, 需要补充根节点是 key 的处理逻辑
TreeNode* deleteNode(TreeNode* root, int key) {
if (root == nullptr) {
return nullptr;
}
if (root->val < key) {
root->right = deleteNode(root->right, key);
} else if (root->val > key) {
root->left = deleteNode(root->left, key);
} else if (root->val == key) {
// 补充删除根节点逻辑
}
return root;
}
2.删除节点有几种可能性, 从简单到复杂详细地分类讨论
(i). 待删除节点是个叶子节点, 删除之后没有任何影响, 直接返回为空指针
(ii). 待删除节点只有左子树或者只有右子树
a.只有左子树, 没有右子树, 让左子树取代当前根节点的位置
b.只有右子树, 没有左子树, 让右子树取代当前根节点的位置
(iii). 待删除节点左子树和右子树是都有的, 那么需要找现在合法的满足单调性的设定, 此时有两种均为合法的选择,
a.找到左子树里面最大的节点换到根节点
b.找到右子树里面最小的节点换到跟节点
(iv). 以右孩子找到最小的节点换过来为例看下如何实现:
a.找到右子树的最小的值节点, 单独 copy 出来, 比如指向 rightMinNode; 单独写一个找最小值的函数, 也就是 BST 的左下角的值
b.在右子树里面删除最小的值对应的节点, 这里递归调用了我们的删除节点的函数
c.rightMinNode 的左子树从原始 root 左子树直接平迁过来, root 的 右子树已经删除了最小节点, 因此也可以平迁过来
// 右子树里面找最小节点
TreeNode* rightMinNode = findMinNode(root->right);
// 先在右子树里面删除这个节点
root->right = deleteNode(root->right, rightMinNode->val);
// 将新的左右子树挂上去
rightMinNode->left = root->left;
rightMinNode->right = root->right;
3.如何找 BST 的最小值? BST 最左下角的节点就是最小值, 直接搜索返回指针
TreeNode* findMinNode(TreeNode* root) {
while (root->left) {
root = root->left;
}
return root;
}
到此为止我们得到答案
class Solution {
public:
TreeNode* findMinNode(TreeNode* root) {
while (root->left) {
root = root->left;
}
return root;
}
TreeNode* deleteNode(TreeNode* root, int key) {
if (root == nullptr) {
return nullptr;
}
if (root->val < key) {
root->right = deleteNode(root->right, key);
} else if (root->val > key) {
root->left = deleteNode(root->left, key);
} else if (root->val == key) {
if (root->left == nullptr && root->right == nullptr) {
return nullptr;
}
if (root->left == nullptr) {
return root->right;
}
if (root->right == nullptr) {
return root->left;
}
TreeNode* rightMinNode = findMinNode(root->right);
root->right = deleteNode(root->right, rightMinNode->val);
rightMinNode->left = root->left;
rightMinNode->right = root->right;
return rightMinNode;
}
return root;
}
};
转载请注明来源, from goldandrabbit.github.io
