前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >逆序数(二叉查找树)

逆序数(二叉查找树)

作者头像
小飞侠xp
发布2018-08-28 17:54:37
5570
发布2018-08-28 17:54:37
举报
文章被收录于专栏:书山有路勤为径

已知数组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]

代码语言:javascript
复制
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; 。。。 思考:将元素按照原数组逆置后的顺序插入到二叉树查找树中,如何在元素插入时,计算已有多少个元素比当前插入元素小?

代码语言:javascript
复制
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),递归将该节点插入到当前节点右子树。

代码语言:javascript
复制
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;
        }
    }
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2018.07.12 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 思考与分析
  • 算法思路
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档