【BST】在搜索二叉树中，寻找节点数据域在[L,U]范围内的节点

题目：EPI

书上代码的思路是：由于BST的中序遍历的节点是按照升序排列的，所以先找到第一个（按照中序遍历的顺序）大于等于L的节点，然后依次找出这个节点的后继节点中，落在范围[L,U]的节点。

但有一个问题就是，如果二叉树节点没有指向父节点的指针域，这个方法就不可取。何况题目没有要求返回的节点要按照升序排列。所以我写出以下代码，不需要二叉树节点有指向父节点的指针，返回的结果在[L,U]范围，但不是有序的。

void find_larger_or_equal_than_L(const shared_ptr<treenode> root, const int L, vector<shared_ptr<treenode>> &res)
{
	if (root == nullptr)
		return;
	if (root->data < L)
	{
		find_larger_or_equal_than_L(root->right, L, res);
		return;
	}
	res.push_back(root);
	find_larger_or_equal_than_L(root->left, L, res);
	find_larger_or_equal_than_L(root->right, L, res);	
}

void find_smaller_or_equal_than_U(const shared_ptr<treenode> root, const int U, vector<shared_ptr<treenode>> &res)
{
	if (root == nullptr)
		return;
	if (root->data >U)
	{
		find_smaller_or_equal_than_U(root->left, U, res);
		return;
	}
	res.push_back(root);
	find_smaller_or_equal_than_U(root->left, U, res);
	find_smaller_or_equal_than_U(root->right, U, res);
}

vector<shared_ptr<treenode>> find_range_nodes(const shared_ptr<treenode> root, const int L, const int U)
{
	vector<shared_ptr<treenode>> res;
	if (root == nullptr || L>U)
		return res;
	//找一个范围在[L,U]的节点
	shared_ptr<treenode> cur = root;
	while (cur)
	{
		if (cur->data < L)
			cur = cur->right;
		else if (cur->data > U)
			cur = cur->left;
		else
			break;
	}
	if (cur == nullptr)
		return res;
	res.push_back(cur);//cur符合要求， 插入res
	find_larger_or_equal_than_L(cur->left, L,res);//cur的左子树中大于等于L的节点插入res
	find_smaller_or_equal_than_U(cur->right, U, res);//cur的右子树中小于等于U的节点插入res
	return res;
}