类似找最大BST subtree, bottom up.
bool findsubtree(TreeNode *node, unordered_set &set, vector
&vec) {
if(not node) {
return true;
}
unordered_set leftset;
unordered_set rightset;
bool left = findsubtree(node->left, leftset, vec);
bool right = findsubtree(node->right, rightset, vec);
if(left&&right) {
//leftset and rightset overlap
for(auto ele:leftset) {
if(rightset.find(ele)!=rightset.end()) {
return false;
}
}
//leftset and rightset no overlap, check node is in the two sets
if(leftset.find(node->val)!=leftset.end()||rightset.find(node->val)!
=rightset.end()) {
return false;
} else {
set.insert(node->val);
set.insert(leftset.begin(), leftset.end());
set.insert(rightset.begin(), rightset.end());
vec.push_back(node);
return true;
}
} else {
return false;
}
}
vector find(TreeNode *node) {
vector vec;
unordered_set set;
findsubtree(node, set, vec);
return vec;
}