C++ binary tree. 92% beats


  • 3
    E
    struct Node
    {
    	Node *left;
    	Node *right;
    	int height;
    	int countPer;
    	int actualCount;
    	Node(int value, int noofper,int real)
    	{
    		this->height  = value;
    		countPer = noofper;
    		left = NULL;
    		right = NULL;
    		actualCount = real;
    	}
    };
    class BinaryTree {
    public:
    	void insert(int value, int countPer)
    	{
    		person = insert(person, value, countPer, countPer);
    	}
    	void inorder(Node* person,vector<pair<int, int>> & result)
    	{
    		if (person == NULL) return;
    		inorder(person->left,result);
    		cout << "{"<<person->height << " " << person->countPer << "} ";
    		result.push_back({ person->height,person->actualCount });
    		inorder(person->right,result);
    	}
    	Node* person;
    	BinaryTree()
    	{
    		person = NULL;
    		}
    private:
    	Node* insert(Node* person, int value, int countPer,int real)
    	{
    		if (person == NULL) return new Node(value, 1,real);
    		if (countPer < person->countPer)
    		{
    			person->left = insert(person->left, value, countPer,real);
    			person->countPer++;
    		}
    		else
    		{
    			person->right = insert(person->right, value, countPer - person->countPer,real);
    		}
    		return person;
    	}
    	int countOf(Node *person)
    	{
    		if (person == NULL) return 1;
    		return person->countPer;
    	}
    };
    
    bool compare(pair<int, int> p1, pair<int, int> p2)
    {
    	if (p1.first == p2.first) return p1.second < p2.second;
    	return p1.first > p2.first;
    }
    
    class Solution {
    public:
    	vector<pair<int, int>> reconstructQueue(vector<pair<int, int>>& people) {
    		BinaryTree btree;
    		sort(people.begin(), people.end(), compare);
    		for (int i = 0; i < people.size(); i++)
    		{
    			cout << people[i].first << " " << people[i].second << endl;
    			btree.insert(people[i].first, people[i].second);
    		}
    		vector<pair<int, int>> result;
    		btree.inorder(btree.person,result);
    		return result;
    	}
    };```

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.