<commit_before>#include <string>
#include <vector>
#include <iostream>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <sstream>
#include <algorithm>
#include <bitset>
#include <numeric>
#include <math.h>
#include <assert.h>
#include <time.h>
#include <stdint.h>

using namespace std;

class mytimer
{
private:
	time_t start_;
public:
	mytimer()
	{
		start_ = time(NULL);
	}
	~mytimer()
	{
		time_t end = time(NULL);
		cout << end - start_ << "s" << endl;
	}
};

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
	bool dfs(TreeNode* root, vector<TreeNode*>& path, int val) {
		if (root == NULL)
		{
			return false;
		}
		if (root->val == val)
		{
			path.push_back(root);
			return true;
		}
		path.push_back(root);
		if (dfs(root->left, path, val))
		{
			return true;
		}
		if (dfs(root->right, path, val))
		{
			return true;
		}
		path.pop_back();
		return false;
	}
	TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
		if (root == NULL || p == NULL || q == NULL)
		{
			return NULL;
		}
		if (p == q)
		{
			return p;
		}
		if (p == root || q == root)
		{
			return root;
		}
		vector<TreeNode*> ppath;
		vector<TreeNode*> qpath;
		if (!dfs(root, ppath, p->val) || !dfs(root, qpath, q->val))
		{
			return NULL;
		}
		size_t i = 0;
		for (; i < ppath.size() && i < qpath.size(); ++i)
		{
			if (ppath[i] != qpath[i])
			{
				return ppath[i - 1];
			}
		}
		if (ppath.size() < qpath.size())
		{
			return p;
		}
		if (ppath.size() > qpath.size())<commit_msg>make use of bst<commit_after>#include <string>
#include <vector>
#include <iostream>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <sstream>
#include <algorithm>
#include <bitset>
#include <numeric>
#include <math.h>
#include <assert.h>
#include <time.h>
#include <stdint.h>

using namespace std;

class mytimer
{
private:
	time_t start_;
public:
	mytimer()
	{
		start_ = time(NULL);
	}
	~mytimer()
	{
		time_t end = time(NULL);
		cout << end - start_ << "s" << endl;
	}
};

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
	bool dfs(TreeNode* root, vector<TreeNode*>& path, int val) {
		if (root == NULL)
		{
			return false;
		}
		if (root->val == val)
		{
			path.push_back(root);
			return true;
		}
		path.push_back(root);
		if (dfs(root->left, path, val))
		{
			return true;
		}
		if (dfs(root->right, path, val))
		{
			return true;
		}
		path.pop_back();
		return false;
	}
	TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
		if (root == NULL || p == NULL || q == NULL)
		{
			return NULL;
		}
		if (p == q)
		{
			return p;
		}
		if (p == root || q == root)
		{
			return root;
		}
/*
		while (1)
		{
			if (p->val < root->val && q->val < root->val && root->left != NULL)
			{
				root = root->left;
				continue;
			}
			if (p->val > root->val && q->val > root->val && root->right != NULL)
			{
				root = root->right;
				continue;
			}
			return root;
		}
*/
		vector<TreeNode*> ppath;
		vector<TreeNode*> qpath;
/*
 		if (p->val < root->val && q->val < root->val)
		{
			return lowestCommonAncestor(root->left, p, q);
		}
		if (p->val > root->val && q->val > root->val)
		{
			return lowestCommonAncestor(root->right, p, q);
		}
*/
		if (!dfs(root, ppath, p->val) || !dfs(root, qpath, q->val))
		{
			return NULL;
		}
		size_t i = 0;
		for (; i < ppath.size() && i < qpath.size(); ++i)
		{
			if (ppath[i] != qpath[i])
			{
				return ppath[i - 1];
			}
		}
		if (ppath.size() < qpath.size())
		{
			return p;
		}
		if (ppath.size() > qpath.size())
{'fraction_non_alphanumeric': 0.18685567010309279, 'fraction_numerical': 0.001288659793814433, 'mean_word_length': 2.9683026584867074, 'pattern_counts': {'":': 0, '<': 67, '<?xml version=': 0, '>': 83, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '5935717', 'n_tokens_mistral': 1780, 'n_tokens_neox': 1600, 'n_words': 386}