mwxjmmyjfm
BAN USERSorry, didn't see the problem clearly. If it must be iterative, we can use the nonrecursive post-order traversal algorithm. The code may be like this:
class Node {
public:
int data;
int height;
Node* left;
Node* right;
Node(int d) : data(d), height(-1), left(NULL), right(NULL) {}
~Node() {
if (left) delete left;
if (right) delete right;
left = right = NULL;
}
};
bool IsBalanced(Node* r) {
if (!r) return true;
std::stack<Node*> s;
Node* cur = r;
Node* pre = NULL;
while (cur || !s.empty()) {
while (cur) {
s.push(cur);
cur = cur->left;
}
cur = s.top();
if (!cur->right || cur->right == pre) {
if (!cur->right) {
if (!cur->left) {
cur->height = 1;
} else {
if ((cur->left)->height > 1) return false;
cur->height = cur->left->height + 1;
}
} else {
int lheight = cur->left->height;
int rheight = cur->right->height;
if (abs(lheight - rheight) > 1) return false;
cur->height = 1 + (lheight > rheight ? lheight : rheight);
}
// visit this node
//std::cout << cur->data << std::endl;
s.pop();
pre = cur;
cur = NULL;
} else {
cur = cur->right;
}
}
return true;
}
If the tree node's content can not be modified, we can copy the tree first, and then traverse the new tree.
The time complexity is O(n), space complexity is also O(n).
Unfortunately, the time complexity in worst case is O(n^2). The formula is:
T(n) = O(n) + T(k) + T(n - k), where k is the number of the negatives. So, if there is only one negative, the formula will change to T(n) = O(n) + T(n - 1) + O(1) = T(n -1) + O(n) = O(n^2).
eg. 1 2 3 4 5 6 -1
Using a map to store the mapping between the old node and the new node
#include <assert.h>
#include <vector>
#include <map>
#include <iostream>
class Node {
public:
int data;
std::vector<Node*> neighbors;
Node(int d) : data(d) {
neighbors.clear();
}
void Insert(Node* t) {
neighbors.push_back(t);
}
};
void CopyGraphImpl(Node* r, Node*& r1, std::map<Node*, Node*>& m) {
int i;
std::map<Node*, Node*>::iterator mitr;
for (i = 0; i < r->neighbors.size(); ++i) {
if ((mitr = m.find(r->neighbors[i])) != m.end()) {
r1->Insert(mitr->second);
continue;
}
Node* t = new Node(r->neighbors[i]->data);
assert(t);
r1->Insert(t);
m.insert(std::make_pair(r->neighbors[i], t));
CopyGraphImpl(r->neighbors[i], t, m);
}
}
void CopyGraph(Node* r, Node*& r1) {
if (!r) return;
if (!r1) {
r1 = new Node(r->data);
assert(r1);
}
std::map<Node*, Node*> m;
m.insert(std::make_pair(r, r1));
CopyGraphImpl(r, r1, m);
}
record the height of the tree when you traverse the tree recursively
class Node {
public:
int data;
Node* left;
Node* right;
Node(int d) : data(d), left(NULL), right(NULL) {}
~Node() {
if (left) delete left;
if (right) delete right;
left = right = NULL;
}
};
bool IsBalanced(Node* r, int& height) {
if (!r) {
height = 0;
return true;
}
int rheight = 0;
int lheight = 0;
if (!IsBalanced(r->left, lheight)) {
return false;
}
if (!IsBalanced(r->right, rheight)) {
return false;
}
if (abs(lheight - rheight) > 1) {
return false;
}
height = 1 + (lheight > rheight ? lheight : rheight);
return true;
}
If the array does not contain duplicated numbers, The algorithm's time complexity is O(n^2)。
- mwxjmmyjfm September 13, 2013But if not, let's set the array {-3, -3, 0, 3}.
is the output:
-3, 0, 3
or:
-3, 0, 3 and -3, 0, 3?
should we print all the duplicated triplets?
If yes, I guess the problem is much more complex.
Some one can give the code?