精华内容
下载资源
问答
  • 动态规划-最小二叉搜索树(OBST)

    千次阅读 2016-04-10 14:33:09
    二叉查找树是按照二叉树结构来组织的,因此可以用二叉链表...构造三个表,w表存储各节点出现频率,e表存储最优二叉搜索树的搜索成本期望值,root表存储最优子树的树根。 根据三个表,可以利用递归来构建最优二叉搜

    二叉查找树是按照二叉树结构来组织的,因此可以用二叉链表结构表示。二叉查找树中的关键字的存储方式满足的特征是:设x为二叉查找树中的一个结点。如果y是x的左子树中的一个结点,则key[y]≤key[x]。

    递归解法(盗图~)


    构造三个表,w表存储各节点出现频率,e表存储最优二叉搜索树的搜索成本期望值,root表存储最优子树的树根。



    根据三个表,可以利用递归来构建最优二叉搜索树。

    package com.qing.org.algorithm;
    /**
     * optimal binary search trees
     * 动态规划实现,O(n3)
     * @author Qing
     *
     */
    public class OBST {
    	public static final int N = 6;
    	public static final double[] p = {0,0.24,0.18,0.09,0.13,0.3,0.06};
    	public static double[][] w = new double[N+2][N+1];
    	public static double[][] e = new double[N+2][N+1];//ki到kj最优二叉树的搜索成本期望值
    	public static int[][] root = new int[N+1][N+1];
    	
    	//构造三个表w,e,root
    	public static void optimalBST(){
    		double t = 0;
    		int j = 0;
    		for(int l = 1; l <= N; l ++){//l是表格对角线,树的深度
    			for(int i = 1; i <= N-l+1; i ++){//只需要计算j>=i的值
    				j = i + l -1;
    				e[i][j] = Integer.MAX_VALUE;//初始值设置为最大
    				w[i][j] = w[i][j-1] + p[j];
    				for(int r = i; r <= j; r ++){
    					t = e[i][r - 1] + e[r+1][j] + w[i][j];//搜索成本为左子树和右子树的搜索成本加根的
    					if(t < e[i][j]){//选择最小搜索成本
    						e[i][j] = t;
    						root[i][j] = r;//r为选出的根
    					}
    				}
    			}						
    		}
    	}
    	//根据三张表w,e,root构造最小二叉搜索树
    	public static void constructOBST(){
    		int r = root[1][N];
    		System.out.println("k" + r);
    		construct_OPT_OBST(1, r-1,"left",r);
    		construct_OPT_OBST(r+1,N,"right",r);
    	}
    	//利用递归构造子树
    	public static void construct_OPT_OBST(int start, int end, String dir, int r){
    		if(start <= end && r >0){
    			int t = root[start][end];
    			System.out.println("k" + t +" is k" + r +"'s" + dir +" tree");
    			construct_OPT_OBST(start, t-1,"left",t);
    			construct_OPT_OBST(t + 1, end,"right",t);
    		}
    	}
    	
    	//打印数组
    	public static void print(int[][] a){
    		int length = a.length;
    		int width = a[0].length;
    		
    		for(int i = 0; i < length; i ++){
    			for(int j = 0; j < width; j ++){
    				System.out.print(a[i][j] + " ");
    			}
    			System.out.println(" ");
    		}
    	}
    	public static void print(double[][] a){
    		int length = a.length;
    		int width = a[0].length;
    		
    		for(int i = 0; i < length; i ++){
    			for(int j = 0; j < width; j ++){
    				System.out.print(a[i][j] + " ");
    			}
    			System.out.println(" ");
    		}
    	}
    	
    	public static void main(String[] args){
    		 optimalBST();
    		 System.out.println("the w :");
    		 print(w);
    		 System.out.println("the e:");
    		 print(e);
    		 System.out.println("the root:");
    		 print(root);
    		 constructOBST();
    	}
    }
    

    测试结果:

    出现了!传说中的double相加问题,虽然对最后的构造结果是没有什么影响,但是若是想将double相加的值得到准确结果,请使用BigDecimal并且一定要用String来够造。

     BigDecimal b1 = new BigDecimal(Double.toString(v1));  
     BigDecimal b2 = new BigDecimal(Double.toString(v2));  
     return b1.add(b2).doubleValue();  
    本算法及其实现参考算法之道第二版第4章动态规划

    展开全文
  • 4.3 Given a sorted (increasing order) array with unique integer elements, write an algorithm to create a binary search tree with ...这道题给了我们一个有序的数组,让我们来生成一个最小高度的二叉搜索树...

    4.3 Given a sorted (increasing order) array with unique integer elements, write an algorithm to create a binary search tree with minimal height.

    这道题给了我们一个有序的数组,让我们来生成一个最小高度的二叉搜索树,为了达到最小高度,肯定是尽可能的填成一个满二叉树,左子树填满,右子树尽可能的填满。而且要注意是二叉搜索树,左<根<右的性质不能忘。既然给了我们一个有序的数组,那么我们可以取中间的数字为根节点,然后左半段为左子树,右半段为右子树,然后再递归去分别再分,有点像二叉搜索法的原理,代码不复杂,也不难懂,如下所示:

    class Solution {
    public:
        TreeNode* createMinimalBST(vector<int> &nums) {
            return createMinimalBST(nums, 0, nums.size() - 1);
        }
        TreeNode* createMinimalBST(vector<int> &nums, int start, int end) {
            if (start > end) return NULL;
            int mid = (start + end) / 2;
            TreeNode *node = new TreeNode(nums[mid]);
            node->left = createMinimalBST(nums, start, mid - 1);
            node->right = createMinimalBST(nums, mid + 1, end);
            return node;
        }
    };

    本文转自博客园Grandyang的博客,原文链接:创建最小二叉搜索树[CareerCup] 4.3 Create Minimal Binary Search Tree ,如需转载请自行联系原博主。

    展开全文
  • 文章目录问题:二叉搜索树结点最小距离解题思路C++代码 问题:二叉搜索树结点最小距离 问题链接 解题思路 二叉搜索树的中序遍历是一个递增的序列,相差最小的节点在中序遍历中相邻,因此进行中序遍历,并进行取差...

    问题:二叉搜索树结点最小距离

    问题链接
    在这里插入图片描述

    解题思路

    二叉搜索树的中序遍历是一个递增的序列,相差最小的节点在中序遍历中相邻,因此进行中序遍历,并进行取差即可。

    C++代码

    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        int minDiffInBST(TreeNode* root) {
            //中序遍历是一个递增的序列,相差最小的节点在中序遍历中相邻
            int pre = 0x3f3f3f3f, ans = 0x3f3f3f3f;//pre表示上次被访问的节点值
            stack<TreeNode*>s;
            //进行中序遍历
            while(root){
                while(root){
                    s.push(root);//入栈,先访问左子树
                    root = root->left;
                }
                while(!s.empty()){
                    TreeNode *tmp = s.top();
                    s.pop();
                    ans = min(ans, abs(tmp->val - pre));
                    pre = tmp->val;//更新上一次被访问的节点值
                    if(tmp->right){//tmp有右子树,访问右子树
                        root = tmp->right;
                        break;
                    }
                }
            }
            return ans;
        }
    };
    
    展开全文
  • 给定一个二叉搜索树,编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。 说明: 你可以假设 k 总是有效的,1 ≤ k ≤ 二叉搜索树元素个数。 进阶: 如果二叉搜索树经常被修改(插入/删除操

    1、把二叉搜索树转换为累加树(538)

    题目描述:

    【简单题】
    在这里插入图片描述

    题目链接

    思路分析
    在这里插入图片描述

    \quad \quad题目要求每一节点的值在原来的基础上加上所有大于其节点的值。考虑二叉搜索树的性质:左子树的节点小于根结点,根结点小于右子树节点,且左子树与右子树均为二叉搜索树。因此,节点值的更新:根结点加上右子树的值,左子树加上右子树以及根结点的值。

    \quad \quad观察累加前中序遍历与累加后中序遍历,我们会发现,其实后者就是前者的一个从后的累加结果。那问题就迎刃而解了,我们只需反向中序遍历即可,并把每次的节点值进行累加,就能得到最终的累加树。而且这样保证了我们对每个节点只访问了一次。

    题解一:反向中序遍历—递归法

    【python代码实现】

    # Definition for a binary tree node.
    # class TreeNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution(object):
        def convertBST(self, root):
            """
            :type root: TreeNode
            :rtype: TreeNode
            """
            self.cur=0
            def inorder_reverse(root):
                
                if not root:
                    return
                inorder_reverse(root.right)
                self.cur+=root.val
                root.val=self.cur
                inorder_reverse(root.left)
                return root
            return inorder_reverse(root)
    

    时间复杂度:O(N)O(N),其中N为树的节点
    空间复杂度:O(h)O(h),函数调用栈的空间,h为树的高度
    题解一:反向中序遍历—迭代法

    # Definition for a binary tree node.
    # class TreeNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution(object):
        def convertBST(self, root):
            """
            :type root: TreeNode
            :rtype: TreeNode
            """
            cur,stack,p=0,[],root
            while p or stack:
                while p:
                    stack.append(p)
                    p=root.right
                p=stack.pop()
                cur+=p.val
                p.val=cur
                p=p.left
            return root
    

    2、二叉搜索树中第K小的元素(230)

    题目描述:

    【中等题】

    给定一个二叉搜索树,编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。

    说明:
    你可以假设 k 总是有效的,1 ≤ k ≤ 二叉搜索树元素个数。

    在这里插入图片描述
    进阶:
    如果二叉搜索树经常被修改(插入/删除操作)并且你需要频繁地查找第 k 小的值,你将如何优化 kthSmallest 函数?

    题目链接

    思路分析

    3、二叉搜索树的最小绝对差(530)

    题目描述:

    【简单题】
    在这里插入图片描述
    题目链接

    思路分析

    1、题目要求:任意两节点的差的绝对值的最小值。
    2、二叉搜索树的中序遍历是递增序列
    3、任意两节点的差的绝对值的最小值只能是所有二叉搜索树右左相邻两节点差值的最小值。
    4、流程:

    • 中序遍历二叉搜索树得到一个列表
    • 列表相邻两值相减得到差值列表
    • 返回差值最小值。

    【python代码实现】——手写,首次尝试

    # Definition for a binary tree node.
    # class TreeNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution(object):
        def getMinimumDifference(self, root):
            """
            :type root: TreeNode
            :rtype: int
            """
            res=[]
            result=[]
            def inorder(root):
                if root is None:
                    return 
                inorder(root.left)
                res.append(root.val)
                inorder(root.right)
                return res
            inorder(root)
            for i in range(len(res)-1):
                a=res[i+1]-res[i]
                result.append(a)
            return min(result)
    
    
    • 参考题解,喜获代码简洁有效的一个版本,下面重现一下
    • 中序遍历二叉搜索树,第一个结点外的每个节点与其前一节点的差值,如果该值小于最小绝对差,就用它更新最小绝对差(初始可设为无穷)。

    【python3 代码实现】

    # Definition for a binary tree node.
    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution:
        def getMinimumDifference(self, root: TreeNode) -> int:
            preval=float('-inf')#前一节点值初始化为负无穷大
            minDiff=float('inf')#绝对值初始化为无穷大
            def inorder(root):
                nonlocal preval,minDiff
                if root is None:
                    return 
                inorder(root.left)
                minDiff=min(minDiff,root.val-preval)
                preval=root.val
                inorder(root.right)
            inorder(root)    
            return minDiff
    

    时间复杂度:O(N),N为树中节点个数。
    空间复杂度:O(h)。h为树的高度

    4、两数之和IV(653)

    题目描述:

    【简单题】
    给定一个二叉搜索树和一个目标结果,如果 BST 中存在两个元素且它们的和等于给定的目标结果,则返回 true。
    在这里插入图片描述
    题目链接

    思路分析

    题解一:中序遍历+双指针法

    1、二叉搜索树的中序遍历是一个有序序列,可将其遍历存储在列表中。
    2、在上述创建的有序列表种使用双指针法
    初始:

    • 左指针l指向最初位置0,右指针r指向末尾位置(列表的长度减1)

    迭代:

    • 当左指针l<右指针r:

      • 如果左指针与右指针两位置和等于目标值,则查找成功
      • 如果左指针与右指针两位置和小于目标值,则左指针+1
      • 如果左指针与右指针两位置和大于目标值,则右指针-1

    【python代码实现】

    # Definition for a binary tree node.
    # class TreeNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution(object):
        def findTarget(self, root, k):
            """
            :type root: TreeNode
            :type k: int
            :rtype: bool
            """
            def inorder(root):
                if root is None:
                    return []
                return inorder(root.left)+[root.val]+inorder(root.right)
            arr=inorder(root)
            l,r=0,len(arr)-1
            while l<r:
                if arr[l]+arr[r]==k:
                    return True
                elif arr[l]+arr[r]<k:
                    l+=1
                else:
                    r-=1
    

    题解二:遍历+哈希表(hashset)

    定义一个辅助函数
    1、初始:

    • 定义空的哈希表

    2、遍历根结点:

    • 如果根结点为空,返回False

    • 如果目标值减去根结点的差值在哈希表中,返回True

    • 否则,将根结点加入到根结点中

    • 接着递归遍历树的左孩子与右孩子,返回左孩子或者右孩子的函数值

    【python代码实现】

    # Definition for a binary tree node.
    # class TreeNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution(object):
        def findTarget(self, root, k):
            """
            :type root: TreeNode
            :type k: int
            :rtype: bool
            """
            hashSet=set()
            def helper(root, k,hashSet):
                if not root:
                    return False
                
                if k - root.val in hashSet:
                    return True
                else:
                    hashSet.add(root.val)
    
                return helper(root.left, k,hashSet) or helper(root.right, k,hashSet)
            
            return helper(root, k,hashSet)
    
    展开全文
  • 530. 二叉搜索树最小绝对差 给你一棵所有节点为非负值的二叉搜索树,请你计算树中任意两节点的差的绝对值的最小值。 输入: 1 \ 3 / 2 输出: 1 解释: 最小绝对差为 1,其中 2 和 1 的差的绝对值为 1...
  • 二叉搜索树节点最小距离: 题解: 二叉搜索树中序遍历是有序的,因此最小差值一定出现在两个相邻的节点中 只要按照顺序遍历的时候,保存前一个节点的值与现在的值的差,与当前最小值做比较即可得到结果 ...
  • 文章目录问题:验证二叉搜索树解题思路C++代码 问题:验证二叉搜索树 问题链接 解题思路 由于BST是递归定义的数据结构,因此我们采用递归的思路进行判断。 空树和只有一个节点的树可以视为BST root有左子树,判断...
  • 783. 二叉搜索树节点最小距离 给你一个二叉搜索树的根节点 root ,返回 树中任意两不同节点值之间的最小差值 。 注意:本题与 530:https://leetcode-cn.com/problems/minimum-absolute-difference-in-bst/ 相同 ...
  • 给定一个所有节点为非负值的二叉搜索树,求树中任意两节点的差的绝对值的最小值。 示例 : 输入: 1 \ 3 / 2 输出: 1 解释: 最小绝对差为1,其中 2 和 1 的差的绝对值为 1(或者 2 和 3)。 注意:树中...
  • 借助中序遍历,元素会按照顺序输出的特点 package FTree;... * 给你一棵所有节点为非负值的二叉搜索树, * 请你计算树中任意两节点的差的绝对值的最小值。 * */ public class Problem530 { /...
  • 给你一棵所有节点为非负值的二叉搜索树,请你计算树中任意两节点的差的绝对值的最小值。 示例: 输入: 1 3 / 2 输出: 1 解释: 最小绝对差为 1,其中 2 和 1 的差的绝对值为 1(或者 2 和 3)。 思路: 二叉搜索...
  • 二叉搜索树———二叉搜索树的删除操作 我们把二叉搜索树的删除分为三种情况 第一种:没有孩子节点直接删除 如图删除 7,4,2直接删除接可以 第二种:只有一个孩子节点把孩子节点拉上去即可 如图:删除6把7拉上去 第三种...
  • 一、什么是二叉搜索树 ...二叉搜索树拥有很高的查找效率,树中最左节点为最小元素,最右节点为最大元素 二、二叉搜索树的实现(查找、插入、删除) 代码如下: #include<iostream> using namespac
  • 给定一个二叉搜索树,同时给定最小边界L和最大边界R。通过修剪二叉搜索树,使得所有节点的值在[L, R]中 (R>=L) 。你可能需要改变树的根节点,所以结果应当返回修剪好的二叉搜索树的新的根节点。 示例 1: 输入:...
  • 二叉搜索树中第k大元素Problem statement: 问题陈述: Find the k-th smallest element in a given binary search tree (BST). 在给定的二进制搜索树(BST)中找到第k个最小的元素。 Example: 例: K=4 Kth ...
  • 二叉搜索树最小绝对差 & 783. 二叉搜索树结点最小距离 给你一棵所有节点为非负值的二叉搜索树,请你计算树中任意两节点的差的绝对值的最小值。 示例: 输入: 1 \ 3 / 2 输出: 1 解释:最小绝对差为...
  • 给定一个有序整数数组,元素各不相同且按升序排列,编写一个算法,创建一棵高度最小二叉搜索树。示例:给定有序数组: [-10,-3,0,5,9],一个可能的答案是:[0,-3,9,-10,null,5],它可以表示下面这个高度平衡二叉搜索...
  • 调用 next() 将返回二叉搜索树中的下一个最小的数。 示例: BSTIterator iterator = new BSTIterator(root); iterator.next(); // 返回 3 iterator.next(); // 返回 7 iterator.hasNext(); // 返回 true...
  • 700. 二叉搜索树中的搜索 题目要求 给定二叉搜索树(BST)的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在,则返回 NULL。 例如 给定二叉搜索树: 4 ...
  • 二叉搜索树节点最小距离

    千次阅读 2020-06-27 11:03:29
    二叉搜索树节点最小距离(力扣:783) 给定一个二叉搜索树的根节点 root,返回树中任意两节点的差的最小值。
  • 调用 next() 将返回二叉搜索树中的下一个最小的数。 示例: BSTIterator iterator = new BSTIterator(root); iterator.next(); // 返回 3 iterator.next(); // 返回 7 iterator.hasNext(); // 返回 true iterator....
  • 177. 把排序数组转换为高度最小二叉搜索树。 给一个排序数组(从小到大),将其转换为一棵高度最小二叉搜索树。 样例 样例 1: 输入:[] 输出:{} 解释:二叉搜索树为空 样例 2: 输入:[1,2,3,4,5,6,7] ...
  • 本文实例讲述了Java删除二叉搜索树最大元素和最小元素的方法。分享给大家供大家参考,具体如下:在前面一篇《Java二叉搜索树遍历操作》中完成了树的遍历,这一节中将对如何从二叉搜索树中删除最大元素和最小元素做...
  • 给你一个二叉搜索树的根节点 root ,返回 树中任意两不同节点值之间的最小差值 。 示例 1: 输入:root = [4,2,6,1,3] 输出:1 示例 2: 输入:root = [1,0,48,null,null,12,49] 输出:1 提示: 树中节点数目在...
  • //空的二叉搜索树,返回NULL else if(!BST->Left) return BST;//找到最左叶结点并返回 else return FindMin(BST->Left);//沿左分支继续查找 } Position FindMax(BinTree BST)//查找最大元素的迭代函数 { if...
  • 给定一个所有节点为非负值的二叉搜索树,求树中任意两节点的差的绝对值的最小值。示例 :输入: 1 \ 3 / 2 输出: 1 解释: 最小绝对差为1,其中 2 和 1 的差的绝对值为 1(或者 2 和 3)。 注意: 树中至少有2...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,579
精华内容 1,031
关键字:

最小二叉搜索树