Josh
BAN USERWe simply need to pass down the minimum value of all Nodes above the current Node, which is updated at each level of the stack frame. Then, return the # Nodes below you which are less than their upper Nodes, plus one if current Node is less than its upper Nodes
struct Node {
Node* left;
Node* right;
int datum;
};
int getNumNodesLowerThanParents(Node* root) {
if(!root) return 0;
return getNumNodesLowerThanParentsHelper(root->left, root->datum) +
getNumNodesLowerThanParentsHelper(root->right, root->datum);
}
int getNumNodesLowerThanParentsHelper(Node* root, int minAbove) {
if(!root) return 0;
int thisAddition = 0;
if(root->datum < minAbove) {
minAbove = root->datum;
++thisAddition;
}
return getNumNodesLowerThanParentsHelper(root->left, minAbove) +
getNumNodesLowerThanParentsHelper(root->right, minAbove) +
thisAddition;
}
Use a stack to do an in-order traversal of both trees. Usual single-tree In-order traversals add on left child until it's NULL, then visit the parent, then recurse right. This algorithm recurses left down the first tree until it finds the NULL child, then pauses as the parent so that it can then do the same with the second tree. One this next "in-order" Node is found, the two are compared. If they are different, we return false. If they are the same, we keep going, recursing right.
struct Node {
Node* left;
Node* right;
char data;
};
bool treesHaveSameInorder(Node* root1, Node* root2) {
if( (!root1 && root2) || (root1 && !root2) ) return false;
if(root1 && root2) return true;
stack<Node*> s1, s2;
s1.push(root1);
s2.push(root2);
Node* trav1 = root1->left;
Node* trav2 = root2->left;
while(!s1.empty() && !s2.empty()) {
while(trav1) {
s1.push(trav1);
trav1 = trav1->left;
}
trav1 = s1.top();
s1.pop();
while(trav2) {
s2.push(trav2);
trav2 = trav2->left;
}
trav2 = s2.top();
s2.pop();
if(trav1->data != trav2->data) return false;
trav1 = trav1->right;
trav2 = trav2->right;
}
if(!s1.empty() || !s2.empty()) return false;
return true;
}
Question is similar to the famous "Box Stacking" problem.
int numNumbers4Apart(int N, int previous, int index,
vector<vector<int>>& numbersAtIndex) {
if(index == N) return 1;
if(previous >= 0 && numbersAtIndex[index][previous] != -1)
return numbersAtIndex[index][previous];
int ways = 0;
for(int i=0; i<10; ++i) {
if(promising(i, previous)) {
ways += numNumbers4Apart(N, i, index+1, numbersAtIndex);
}
}
if(previous >= 0) {
numbersAtIndex[index][previous] = ways;
}
return ways;
}
int N = 5;
vector<vector<int> > numbersAtIndex(N, vector<int>(10, -1));
cout << numNumbers4Apart(N, -3, 0, numbersAtIndex) << endl;
Similar to above, but without an optimization that once you create your digit array from A, you have your highest number
O(N) to parse through A + O(1) memory for digit array + O(1) time to iterate through digit array. O(N) time and O(1) memory.
- Josh August 21, 2015