二叉搜索树的应用问题
二叉搜索树的定义
若左子树不空，则左子树上所有节点的值均小于根节点的值
若右子树不空，则右子树上所有节点的值均大于根节点的值
它的左右子树也均为二叉搜索树
中序遍历结果为一个升序数组
LeeCode 98: 验证二叉搜索树
题目描述
给你一个二叉树的根节点
root，判断其是否是一个有效的二叉搜索树。
建立模型
方法一
中序遍历二叉树，并将结构保存到数组中
判断数组是否为升序
方法二
计算每个节点值的可能区间
若所有节点值均在区间内，则是一棵有效的二叉搜索树，返回 true
若存在节点的值不在所属区间内，则不是一个有效的二叉搜索树 false
由于 \(-2^{31} < node.val < 2^{31} - 1\)，所以Integer类型初始最大值不够，需要Long类型
代码实现
// 方法一
public boolean isValidBST(TreeNode root) {
List<Integer> inorder = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode node = root;
while (node != null || !stack.isEmpty()) {
while (node != null) {
stack.push(node);
node = node.left;
}
node = stack.pop();
inorder.add(node.val);
node = node.right;
}
// 判断中序遍历是否为升序序列
for (int i = 0; i < inorder.size() - 1; i++) {
if (inorder.get(i) >= inorder.get(i + 1)) {
return false;
}
}
return true;
}
// 方法二
public boolean isValidBST(TreeNode root) {
return isValidBSTImpl(root, Long.MAX_VALUE, Long.MIN_VALUE);
}
/**
* @root 当前节点
* @max 节点值上界
* @min 节点值下界
*/
public boolean isValidBSTImpl(TreeNode root, long max, long min) {
if (root == null) {
return true;
}
if (root.val >= max || root.val <= min) {
return false;
}
return isValidBSTImpl(root.left, root.val, min) && isValidBSTImpl(root.right, max, root.val);
}
LeeCode 235: 二叉搜索树的最近公共祖先
题目描述
给定一个二叉搜索树，找到该树中两个指定节点的最近公共祖先。
建立模型
不同于二叉树的最近公共祖先，本题是一棵二叉搜索树
可以通过节点值的大小关系来判断存在于左子树还是右子树
代码实现
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || root == p || root == q) {
return root;
}
TreeNode node = null;
if (p.val < root.val && q.val < root.val) {
node = lowestCommonAncestor(root.left, p, q);
}
else if(p.val > root.val && q.val > root.val) {
node = lowestCommonAncestor(root.right, p, q);
}
else {
node = root;
}
return node;
}
LeeCode 701: 二叉搜索树的插入操作
题目描述
给定二叉搜索树（BST）的根节点
root和要插入树中的值value，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据保证，新值和原始二叉搜索树中的任意节点值都不同。注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。
建立模型
核心思路：将新增节点插入到对应的空节点
- 若插入节点值大于当前节点，则递归判断其右子节点
若右子节点为空，则将新增节点插入到当前节点的右边
若插入节点值小于当前节点，则递归判断其左子节点
若左子节点为空，则将新增节点插入到当前节点的左边
代码实现
public TreeNode insertIntoBST(TreeNode root, int val) {
TreeNode insert = new TreeNode(val);
if (root == null) {
return insert;
}
TreeNode node = root;
boolean flag = true;
while (flag) {
if (node.val < val) {
if (node.right == null) {
node.right = insert;
flag = false;
}
else {
node = node.right;
}
}
else {
if (node.left == null) {
node.left = insert;
flag = false;
}
else {
node = node.left;
}
}
}
return root;
}
LeeCode 450: 删除二叉搜索树中的节点
题目描述
给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
一般来说，删除节点可分为两个步骤：
首先找到需要删除的节点
如果找到了，删除它
建立模型
- 找到需要删除的节点和它的父节点
若需要删除的节点为父节点的左子节点，则分别讨论需要删除节点的左右子节点是否为空，修改
pre.left域，调整树结构若需要删除的节点为父节点的右子节点，则分别讨论需要删除节点的左右子节点是否为空，修改
pre.right域，调整树结构步骤2，3是一个对称的过程，理解了步骤2也就理解了步骤3
代码实现
public TreeNode deleteNode(TreeNode root, int key) {
// 创建虚拟根节点，从而可以不需要为处理root节点添加额外的讨论
TreeNode virtualHead = new TreeNode((int)(Math.pow(10, 5) + 1));
virtualHead.left = root;
TreeNode pre = virtualHead; // 当前节点的父节点
TreeNode cur = root; // 当前节点
while (cur != null) {
if (cur.val > key) {
pre = cur;
cur = cur.left;
}
else if (cur.val < key) {
pre = cur;
cur = cur.right;
}
// 当前节点为要删除的节点
else {
// 父节点的值大于当前节点，说明需要删除的是左子节点
if (pre.val > key) {
// 当前节点的左右子结点均不为空，调整树结构
// pre -> left 指向 cur.right
// 查找当前节点右子结点的最左节点，将该节点的left指向cur.left
if (cur.right != null && cur.left != null) {
pre.left = cur.right;
TreeNode node = cur.right;
while (node.left != null) {
node = node.left;
}
node.left = cur.left;
}
// 当前节点的右子结点不为空，左子节点为空
// 则直接将 pre.left 指向 cur.right
else if (cur.right != null) {
pre.left = cur.right;
}
// 当前节点的左子结点不为空，右子节点为空
// 则直接将 pre.left 指向 cur.left
else if (cur.left != null) {
pre.left = cur.left;
}
// 当前节点的左右子节点均为空，则直接删除，pre.left 指向空
else {
pre.left = null;
}
}
// 父节点的值小于当前节点的值，说明需要删除的点是右子节点
if (pre.val < key) {
if (cur.right != null && cur.left != null) {
pre.right = cur.left;
TreeNode node = cur.left;
while (node.right != null) {
node = node.right;
}
node.right = cur.right;
}
else if (cur.right != null) {
pre.right = cur.right;
}
else if (cur.left != null) {
pre.right = cur.left;
}
else {
pre.right = null;
}
}
break;
}
}
return virtualHead.left;
}
LeeCode 108: 将有序数组转换为二叉搜索树
题目描述
给你一个整数数组
nums，其中元素已经按升序排列，请你将其转换为一棵高度平衡二叉搜索树。高度平衡 二叉树是一棵满足 每个节点的左右两个子树的高度差不超过1 的二叉树。
建立模型
- 每次去数组的中间值作为根节点
使用左边界到中间值的子数组递归构建左子树
使用中间值到右边界的子数组递归的构建右子树
代码实现
public TreeNode sortedArrayToBST(int[] nums) {
return sortedArrayToBSTImpl(nums, 0, nums.length - 1);
}
public TreeNode sortedArrayToBSTImpl(int[] nums, int left, int right) {
if (left > right) {
return null;
}
int mid = left + (right - left) / 2;
TreeNode node = new TreeNode(nums[mid]);
node.left = sortedArrayToBSTImpl(nums, left, mid - 1);
node.right = sortedArrayToBSTImpl(nums, mid + 1, right);
return node;
}
