You have to make sure that when it calls a push_back
, it's one of the nodes in the path. Since your current algorithm adds nodes for every node.
class Tree {
private:
Node* root;
vector<int> vec; /*.....*/
int calcDepth(Node *n,int isInPath)
{
if (n == NULL)
return 0;
else
{
int ld = calcDepth(n->getLeft(),0);
int rd = calcDepth(n->getRight(),0);
if(isInPath){
vec.push_back(n->getVal());
if (ld > rd)
{
calcDepth(n->getLeft(),isInPath);
return ld + 1;
}
else
{
calcDepth(n->getRight(),isInPath);
return rd + 1;
}
}
return max(ld+1,rd+1);
}
} // end of calcDepth
I've added a variable isInPath
, that is 1 if the current node is in the path, and 0 if it's not. You will call this with the root and 1.
It finds the maximum of the two and only then calls with isInPath == 1
. And with this method, only nodes with isInPath == 1
will be added to the vector.
I haven't tested it out but it should work. You can also create this as a private function and then a public one with only the node value.
Note: This has O(N^2)
complexity. To make it in O(N)
you can memorize the values so you don't compute them 2 times.