C++ solution with in-order path find


#1

#include

 bool findPath(TreeNode* root, int val, list<TreeNode*>& path)
{
	 if (root == nullptr) return false;
	 if (root->val == val) //found
	 {
		 path.push_back(root);
		 return true;
	 }
	 list<TreeNode*> leftPath;
	 if (findPath(root->left, val, leftPath))
	 {
		 path = leftPath;
		 path.push_front(root);
		 return true;
	 }

	 list<TreeNode*> rightPath;
	 if (findPath(root->right, val, rightPath))
	 {
		 path = rightPath;
		 path.push_front(root);
		 return true;
	 }

	 return false;
}
int Solution::lca(TreeNode* A, int B, int C) {

	int result = -1;
	list<TreeNode*> pathToB;

	if (!findPath(A, B, pathToB)) return result;

	list<TreeNode*> pathToC;
	if (!findPath(A, C, pathToC)) return result;
	
	result = (*pathToB.begin())->val;
	
	auto itrB = pathToB.begin();
	auto itrC = pathToC.begin();
	while (itrB != pathToB.end() && itrC != pathToC.end() && (*itrB)->val == (*itrC)->val)
	{
		result = (*itrB)->val;
		++itrB;
		++itrC;
	}

	return result;
}