专栏首页书山有路勤为径逆序数(二叉查找树)

逆序数(二叉查找树)

已知数组nums,求新数组count,count[i]代表了在nums[i]右侧且比nums[i]小的元素个数。 例如: nums = [5,2,6,1], count = [2,1,1,0] nums = [6,6,6,1,1,1], count = [3,3,3,0,0,0]

class Solution{
public:
    std::vector<int> countSmaller(std::vector<int> & nums){}
} ;

LeetCode 315

思考与分析

已知数组nums = [5,-7,9,1,3,5,-2,1],它的逆序数组count = [5,0,5,1,2,2,0,0];数组count[i],为nums[i+1],nums[i+2],...,nums[size()-1]有多少个比nums[i]小的数 或者将数组逆置[1,-2,5,3,1,9,-7,5] 数组count[i]为nums[0],nums[1],...,nums[i-1]中有多少个比nusm[i]小的个数: 1,数组[]中比它小的个数为0; -2,数组[1]中比它个小的数为0; 5,数组[1,-2]中比它小的个数为2; 3,数组[1,-2,5]中比它小的个数为2; 。。。 思考:将元素按照原数组逆置后的顺序插入到二叉树查找树中,如何在元素插入时,计算已有多少个元素比当前插入元素小?

struct BSTNode{
    int val;
    int count;
    BSTNode *left;
    BSTNode *right;
    BSTNode (int x) : val(x), left(NULL),right(NULL),count(0){}
};

在插入节点时,当待插入节点insert_node 小于等于当前node时,count++ 按照[1,-2,5,3,1,9,-7,5]的顺序构建二叉查找树。

算法思路

将元素按住逆置后的顺序插入到二叉查找树中,如何在元素插入时,计算已有多少个元素比当前插入元素小? 5,[1,-2,5,3,1,9,-7]中比它小的数个数为5. 算法如下: 设置变量count_small = 0 ,记录在插入过程中有多少个元素比插入节点值小; 若待插入节点值小于等于当前节点node值,node->count++,递归将该节点插入到当前节点左子树; 若待插入节点值大于当前节点node值,count_small + = node->count + 1;(当前节点左子树数量+1),递归将该节点插入到当前节点右子树。

struct BSTNode{
    int val;
    int count;//二叉树左子树中节点个数
    BSTNode *left;
    BSTNode * right;
    BSTNode(int x) : val(x), left(NULL), right(NULL), count(0){}
};

void BST_insert(BSTNode *node, BSTNode * insert_node, int &count_small){
    if(inser_node->val < node->val){
        node->count++;
        if(node->left){
            BST_insert(node->left, insert_node, count_small);
        }
        else{
            node->left = insert_node;
        }
    }
    else{
        count_small + = node->count +1;
        if(node->rifht){
            BST_insert(node->right, insert_node, count_small);
        }
        else{
            node->right = insert_node;
        }
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 堆的基础知识

    二叉堆是非线性的树形的数据结构,有两种堆,最大堆与最小堆。最大堆,树种各个父 节点的值总是大于或等于任何一个子节点的值;最小堆,树种各个父节点的值总是小于或 等...

    小飞侠xp
  • 二叉查找树

    二叉查找树是一种数据结构,它是具有以下性质的二叉树: 1.若左子树不空,则左子树上所有结点的值均小于或等于它的根结点的值; 2.若右子数不空,则右子树上所有...

    小飞侠xp
  • electron-ssr

    客户端下载地址:https://github.com/qingshuisiyuan/electron-ssr-backup/releases/download/...

    小飞侠xp
  • STL之迭代器

    Iterator(迭代器) 模式又称 Cursor(游标) 模式, 用于提供一种方法顺序访问一个聚合对象中各个元素, 而又不需暴露该对象的内部表示。 或者这样说...

    用户5426759
  • 自已动手作图搞清楚AVL树

    二叉树是一种常用的数据结构,更是实现众多算法的一把利器。 二分搜索树(Binary Search Tree)做为一种能实现快速定位查找的二叉树也得到了广泛应用

    智慧zhuhuix
  • 实现一个二叉搜索树(JavaScript 版)

    二叉树在计算机科学中应用很广泛,学习它有助于让我们写出高效的插入、删除、搜索节点算法。二叉树的节点定义:一个节点最多只有两个节点,分别为左侧节点、右侧节点。

    五月君
  • 【一天一大 lee】二叉树的前序遍历 (难度:中等) - Day20201027

    前端小书童
  • 二叉树的前、中、后遍历(递归/非递归)

    二叉树的遍历 ? 二叉树的前序遍历 访问根结点,先序遍历左子树,先序遍历右子树 遍历基本步骤为先根结点,然后左子树,然后右子树, 需要注意的是这个遍历需要类似于...

    李家酒馆酒保
  • 【一天一大 lee】 把二叉搜索树转换为累加树 (难度:简单)-Day20200921

    给定一个二叉搜索树(Binary Search Tree),把它转换成为累加树(Greater Tree),使得每个节点的值是原来的节点值加上所有大于它的节点值...

    前端小书童
  • openshift/origin工作记录(5)——node节点系统资源预留

    解决思路为设置node节点系统资源预留值。

    胡了了

扫码关注云+社区

领取腾讯云代金券