二叉搜索树(BST)系列

wuchangjian2021-11-03 08:05:29编程学习

二叉搜索树(Binary Search Tree)定义如下:
节点的左子树只包含 小于 当前节点的数。
节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

再刷一遍二叉搜索树

文章目录

  • (一)
    • 230. 二叉搜索树中第K小的元素
    • 538. 把二叉搜索树转换为累加树
  • (二)
    • 98. 验证二叉搜索树
    • 700. 二叉搜索树中的搜索
    • 701. 二叉搜索树中的插入操作
    • 450. 删除二叉搜索树中的节点
  • (三)
    • 96. 不同的二叉搜索树
    • 95. 不同的二叉搜索树 II

(一)

230. 二叉搜索树中第K小的元素

230. 二叉搜索树中第K小的元素
给定一个 二叉搜索树 的根节点 root ,和一个整数 k ,请你设计一个算法查找其中第 k 个最小元素(从 1 开始计数)。

  1. 二叉搜索树 中序遍历的序列,就是一个升序的序列。
  2. 解决这个问题,只要进行中序遍历,得到第 k 个值赋给 res 就可以了
int res = 0;
int index = 0;
public int kthSmallest(TreeNode root, int k) {
	traverse(root, k);
	return res;
}

//中序遍历,将第 k 个值赋给 res 
public void traverse(TreeNode root, int k){
	if(root == null) return;
	traverse(root.left, k);
	index++;
	if(index == k){
		res = root.val;
		return;
	}
	traverse(root.right, k);
}


538. 把二叉搜索树转换为累加树

538. 把二叉搜索树转换为累加树
给出 二叉搜索树 的根节点,该树的节点值各不相同,请你将其转换为累加树(Greater Sum Tree),使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。

//原二叉搜索树的最右叶子节点的节点值最大
public TreeNode convertBST(TreeNode root) {
	traverse(root);
	return root;
}
int sum = 0;
public void traverse(TreeNode root){
	if(root == null) return;
	//从右节点开始累加
	traverse(root.right);
	sum = sum + root.val;
	root.val = sum;
	traverse(root.left);
	return;
}



(二)

98. 验证二叉搜索树

98. 验证二叉搜索树
给你一个二叉树的根节点 root ,判断其是否是一个有效的二叉搜索树。

//每一个节点都要考虑应该大于 [?] 小于 [?]
public boolean isValidBST(TreeNode root) {
	return isTrue(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
}
//力扣测试时可能会有测试数据越界,可将 int 改为 long
public boolean isTrue(TreeNode root, int min, int max){
	if(root == null) return true;
	
	if(root.val <= min || root.val >= max)
		return false;
	//左子树的最大值为当前节点的值,右子树的最小值为当前节点的值
	return isTrue(root.left, min, root.value) && isTrue(root.right, root.val, max);
}


700. 二叉搜索树中的搜索

700. 二叉搜索树中的搜索
给定 二叉搜索树 的根节点和一个值。 你需要在BST中找到 节点值等于给定值 的节点。 返回以该节点为根的子树。 如果节点不存在,则返回 NULL。

  1. 最简单的办法,直接遍历找就可以了。
  2. 在此基础上我们还可以根据二叉搜索树的性质来减少搜索。
public TreeNode searchBST(TreeNode root, int val) {
	if(root == null) return null;
	if(root.val == val) return root;
	if(root.val > val) return searchBST(root.left);
	if(root.val < val) return searchBST(root.right);
	return null;
}


701. 二叉搜索树中的插入操作

701. 二叉搜索树中的插入操作
给定 二叉搜索树 的根节点和要插入树中的值,将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ,新值和原始二叉搜索树中的任意节点值都不同。

  1. 找到正确的位置,将值插入二叉搜索树
public TreeNode insertIntoBST(TreeNode root, int val) {
	if(root == null) return newTreeNode(val);
	if(root.val > val)
		root.left = insertIntoBST(root.left, val);
	if(root.val < val)
		root.right = insertIntoBST(root.right, val);
	return root;
}


450. 删除二叉搜索树中的节点

450. 删除二叉搜索树中的节点
给定一个二叉搜索树的根节点 root 和一个值 key,删除二叉搜索树中的 key 对应的节点,并保证二叉搜索树的性质不变。返回二叉搜索树(有可能被更新)的根节点的引用。

  1. 删除节点,首先要找到节点。寻找给定值的节点即上题 700.二叉搜索树中的搜索,很简单。

  2. 找到后会有这几种情况。
    该节点无左右子节点,可直接删除。
    该节点有左子节点或右子节点,那么删除此节点后,需要让左子节点或右子节点代替被删除节点的位置。
    该节点有左子节点和右子节点,那么删除后还需判断让谁来接替自己的位置。【回忆一下二叉搜索树的特点,右节点 > 根节点 > 左节点,那么删掉根节点后,要找右节点的最小值(或者左节点的最大值)作为根节点】

  3. 先根据 700题 写出框架,再考虑细节问题。

public TreeNode deleteNode(TreeNode root, int key) {
	if(root == null) return null;
	if(root.val == key){
		//三种情况
		//1.无左右子节点
		if(root.left == null && root.right == null) return null;
		//2.有左子节点或右子节点
		if(root.left == null) return root.right;
		if(root.right == null) return root.left;
		//3.有左子节点和右子节点,寻找右子树的最小值作为根节点
		if(root.left != null && root.right != null){
			TreeNode minNode = getMin(root.right);
			root.val = minNode.val;
			//将右子树中值为minNode.val的节点删除
            root.right = deleteNode(root.right, minNode.val);
		}
			
	}else if(root.val > key){
		root.left = deleteNode(root.left, key);	
	}else if(root.val < key){
		root.right = deleteNode(root.right, key);
	}
	return root;
}
//寻找最小值
public TreeNode getMin(TreeNode node){
	//最左的叶子节点是最小的
    while(node.left != null) node = node.left;
    return node;
}



(三)

96. 不同的二叉搜索树

96. 不同的二叉搜索树
给你一个整数 n ,求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种?返回满足题意的二叉搜索树的种数。

  1. 构造一个二叉树,要先考虑根节点。显然此题中 [1,n] 每个数都可以作为根节点。
  2. 遍历每个数作为根节点的情况。
  3. 假如取 x 作为根结点,那么计算这种情况的个数,就看左右子树分别能组成多少不同的二叉树。根节点能组成的情况等于 left ✖ right
  4. left = count ( lo, x-1),right = count ( x+1, hi )
    【函数 count( int lo, int hi ) 计算[lo, hi] 能组成多少不同的二叉树。】
  5. 所以此题是遍历加递归,还存在着重叠子问题。
public int numTrees(int n) {
	return count(1, n);
}
public int count(int lo, int hi){
	//存在递归,记得写跳出递归的条件
	if(lo > hi) return 1;
	//遍历 [lo - hi]
    int res = 0;
    for(int i=lo; i<=hi; i++){
        int left = count(lo, i-1);
        int right = count(i+1, hi);
        res += left * right;
    }
    return res;
}

上面的解法没有解决重叠子问题,只是用穷举解决的。
使用动态规划解法,自底向上的解决问题。

  1. 根据题目看,决定不同二叉树个数的是数组长度,而不是数组内容。
  2. 确定dp[]数组,dp[0] = 1、dp[1] = 1、dp[2] = 2 …,求出dp[n]
public int numTrees(int n) {
	int[] dp = new int[n + 1];
	dp[0] = 1;
	dp[1] = 1;
	//计算dp[i],直到求出dp[n]
	for (int i = 2; i <= n; ++i) {
		//遍历分别以这个数组中的数做根节点的不同二叉树的个数,最后累加得到dp[i]
		//长度为 i, 让 j 做根节点,左边数组长度为[j-1],右边数组长度为[i-j]
		for (int j = 1; j <= i; ++j) {
			//dp[i] = 这些遍历的累加
			dp[i] += dp[j - 1] * dp[i - j];
		}
    }
    return dp[n];
}


95. 不同的二叉搜索树 II

95. 不同的二叉搜索树 II
给你一个整数 n ,请你生成并返回所有由 n 个节点组成且节点值从 1 到 n 互不相同的不同 二叉搜索树 。可以按 任意顺序 返回答案。

  1. 穷举出所有的根节点
  2. 递归构造出所有左右子树【List< TreeNode > 类型】
  3. 利用循环使根节点,连接这些所有的子树
public List<TreeNode> generateTrees(int n) {
    return build(1,n);
}
public List<TreeNode> build(int lo, int hi){
    List<TreeNode> res = new LinkedList<>();
    if(lo > hi){
        res.add(null);
        return res;
    }
	// 穷举 root 节点的所有可能。
    for(int i=lo; i<=hi; i++){
        List<TreeNode> lefts = build(lo, i-1);
        List<TreeNode> rights = build(i+1, hi);
        // 递归构造出左右子树的所有合法 BST。
        for(TreeNode left : lefts ){
            for(TreeNode right : rights){
              	//使用这些左右子树构造二叉树
                TreeNode root = new TreeNode(i);
                root.left = left;
                root.right = right;
                res.add(root);
            }
        }
    }        
    return  res;
}


感谢看到这里😛😛,快去多刷题吧。看的再多,不如沉下心去试一试呀😎

相关文章

彭州山洪灾害致7死8伤:上游未见泥石流,多年前有游客被冲走

彭州山洪灾害致7死8伤:上游未见泥石流,多年前有游客被冲走

2022-08-14 18:37:48 △龙漕沟。图片来源:受访者供图...

Flutter介绍和dart语法解读(上)

Flutter介绍和dart语法解读(上)

Flutter是谷歌的移动UI框架,可以快速在iOS和Android上构建...

非const引用

在c++开发过程中,很容易出现的错误就是非const引用&...

SSO 单点登录.医疗信息系统应用

SSO 单点登录.医疗信息系统应用

  前言:SSO 单点登录   “半...

发表评论    

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。