s****n
发帖数: 220 | 1 今天看到一道面试题，想不出很好的解法，请大牛们过过目，指点下，哈哈。
给定一个二叉树，所有的节点值（包括中间，叶子节点）有可能重复，题目要求找出所
有的没有重复节点的子树（包括叶子节点，这个算作一个节点的子树）。
e.g.
3
2 4
1 5 7 2
总共有6个这样的子树，即除了3之外，所有的节点所对应的子树都符合要求。 |
c********6
发帖数: 33 | 2 不是大牛，来个naive的方法吧：
后续遍历二叉树，
建一个哈希表 key是root节点，value是这颗树的所有节点的值 包括root，
没访问一个节点，看他左右子树哈希表值有没有重复，有的话就不符合，
然后再把左右子树的set merge 加上他自己作为这个节点的值放到哈希表里，
比如说 节点4 左边是 7 右边是 2 没有重合，符合要求， 然后把 4 2 7 座位一个set
放到哈希表里
节点3 左边 1 2 5 右边 4 7 2 有重合 不符合要求， 然后把3 1 2 5 4 7作为 节点3
的set，
因为是post order所以可以保证 左右孩子都算完了再算父节点，
复杂度n2 |
s****n
发帖数: 220 | 3 这个也是我想到的 但是感觉树的题目应该有更好的解法 哈哈
set
3
【在 c********6 的大作中提到】
: 不是大牛，来个naive的方法吧：
: 后续遍历二叉树，
: 建一个哈希表 key是root节点，value是这颗树的所有节点的值 包括root，
: 没访问一个节点，看他左右子树哈希表值有没有重复，有的话就不符合，
: 然后再把左右子树的set merge 加上他自己作为这个节点的值放到哈希表里，
: 比如说 节点4 左边是 7 右边是 2 没有重合，符合要求， 然后把 4 2 7 座位一个set
: 放到哈希表里
: 节点3 左边 1 2 5 右边 4 7 2 有重合 不符合要求， 然后把3 1 2 5 4 7作为 节点3
: 的set，
: 因为是post order所以可以保证 左右孩子都算完了再算父节点，
|
l*********8
发帖数: 4642 | 4 nlogn time吧？
set
3
【在 c********6 的大作中提到】
: 不是大牛，来个naive的方法吧：
: 后续遍历二叉树，
: 建一个哈希表 key是root节点，value是这颗树的所有节点的值 包括root，
: 没访问一个节点，看他左右子树哈希表值有没有重复，有的话就不符合，
: 然后再把左右子树的set merge 加上他自己作为这个节点的值放到哈希表里，
: 比如说 节点4 左边是 7 右边是 2 没有重合，符合要求， 然后把 4 2 7 座位一个set
: 放到哈希表里
: 节点3 左边 1 2 5 右边 4 7 2 有重合 不符合要求， 然后把3 1 2 5 4 7作为 节点3
: 的set，
: 因为是post order所以可以保证 左右孩子都算完了再算父节点，
|
M*****M
发帖数: 20 | 5 类似找最大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;
} |
a*********4
发帖数: 7 | 6 a java solution:
import java.util.*;
public class FindNonDupeSubTree {
private class Node{
int val;
Node left;
Node right;
Node (int val){
this.val = val;
left = null;
right = null;
}
}
public boolean FindSubTree(Node root, Set nodeSet, ArrayList<
Integer> validTreeRoots){
if (root == null)
return true;
Set sleft = new HashSet();
Set sright = new HashSet();
boolean left = FindSubTree(root.left, sleft, validTreeRoots);
boolean right = FindSubTree(root.right, sright, validTreeRoots);
if (left && right){
// both are valid, let's check if left and right has any
overlaps.
for (Integer i : sleft){
if (sright.contains(i))
return false;
}
}
// now there's no overlap between left tree and right tree, check
root is in any of them or not
if (sleft.contains(root.val) || sright.contains(root.val))
return false;
// everything checked out as unique, merge root into all sets, and
add root to the validtreeroots
validTreeRoots.add(root.val);
nodeSet.addAll(sright);
nodeSet.addAll(sleft);
nodeSet.add(root.val);
return true;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
FindNonDupeSubTree ft = new FindNonDupeSubTree();
Node root = ft.new Node(3);
Node temp = null;
temp = ft.new Node(2);
root.left = temp;
temp = ft.new Node(4);
root.right = temp;
temp = ft.new Node(1);
root.left.left = temp;
temp = ft.new Node(5);
root.left.right = temp;
temp = ft.new Node(7);
root.right.left = temp;
temp = ft.new Node(2);
root.right.right = temp;
Set s = new HashSet();
ArrayList v = new ArrayList();
ft.FindSubTree(root, s, v);
System.out.println(v.size());
}
}
*>
【在 M*****M 的大作中提到】
: 类似找最大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);
|
s****n
发帖数: 220 | 7 the nodeset will remove the duplicated elements in the subtree, which will
affect the decision for the parent tree. |
s****n
发帖数: 220 | 8 the nodeset will remove the duplicated elements in the subtree, which will
affect the decision for the parent tree. |
a*********4
发帖数: 7 | 9 nodeset will remove dups, but that won't really impact the result. as long
as there's one copy of the presented nodes in the set, it will serve the
purpose of prevent dupe when comparing two sets. the result is stored in the
arraylist, which will maintain dup as is.
【在 s****n 的大作中提到】
: the nodeset will remove the duplicated elements in the subtree, which will
: affect the decision for the parent tree.
|
r*******k
发帖数: 1423 | 10 就是你这个方法，很好的
一点都不navie
set
3
【在 c********6 的大作中提到】
: 不是大牛，来个naive的方法吧：
: 后续遍历二叉树，
: 建一个哈希表 key是root节点，value是这颗树的所有节点的值 包括root，
: 没访问一个节点，看他左右子树哈希表值有没有重复，有的话就不符合，
: 然后再把左右子树的set merge 加上他自己作为这个节点的值放到哈希表里，
: 比如说 节点4 左边是 7 右边是 2 没有重合，符合要求， 然后把 4 2 7 座位一个set
: 放到哈希表里
: 节点3 左边 1 2 5 右边 4 7 2 有重合 不符合要求， 然后把3 1 2 5 4 7作为 节点3
: 的set，
: 因为是post order所以可以保证 左右孩子都算完了再算父节点，
|
|
|
s****n
发帖数: 220 | 11 今天看到一道面试题，想不出很好的解法，请大牛们过过目，指点下，哈哈。
给定一个二叉树，所有的节点值（包括中间，叶子节点）有可能重复，题目要求找出所
有的没有重复节点的子树（包括叶子节点，这个算作一个节点的子树）。
e.g.
3
2 4
1 5 7 2
总共有6个这样的子树，即除了3之外，所有的节点所对应的子树都符合要求。 |
c********6
发帖数: 33 | 12 不是大牛，来个naive的方法吧：
后续遍历二叉树，
建一个哈希表 key是root节点，value是这颗树的所有节点的值 包括root，
没访问一个节点，看他左右子树哈希表值有没有重复，有的话就不符合，
然后再把左右子树的set merge 加上他自己作为这个节点的值放到哈希表里，
比如说 节点4 左边是 7 右边是 2 没有重合，符合要求， 然后把 4 2 7 座位一个set
放到哈希表里
节点3 左边 1 2 5 右边 4 7 2 有重合 不符合要求， 然后把3 1 2 5 4 7作为 节点3
的set，
因为是post order所以可以保证 左右孩子都算完了再算父节点，
复杂度n2 |
s****n
发帖数: 220 | 13 这个也是我想到的 但是感觉树的题目应该有更好的解法 哈哈
set
3
【在 c********6 的大作中提到】
: 不是大牛，来个naive的方法吧：
: 后续遍历二叉树，
: 建一个哈希表 key是root节点，value是这颗树的所有节点的值 包括root，
: 没访问一个节点，看他左右子树哈希表值有没有重复，有的话就不符合，
: 然后再把左右子树的set merge 加上他自己作为这个节点的值放到哈希表里，
: 比如说 节点4 左边是 7 右边是 2 没有重合，符合要求， 然后把 4 2 7 座位一个set
: 放到哈希表里
: 节点3 左边 1 2 5 右边 4 7 2 有重合 不符合要求， 然后把3 1 2 5 4 7作为 节点3
: 的set，
: 因为是post order所以可以保证 左右孩子都算完了再算父节点，
|
l*********8
发帖数: 4642 | 14 nlogn time吧？
set
3
【在 c********6 的大作中提到】
: 不是大牛，来个naive的方法吧：
: 后续遍历二叉树，
: 建一个哈希表 key是root节点，value是这颗树的所有节点的值 包括root，
: 没访问一个节点，看他左右子树哈希表值有没有重复，有的话就不符合，
: 然后再把左右子树的set merge 加上他自己作为这个节点的值放到哈希表里，
: 比如说 节点4 左边是 7 右边是 2 没有重合，符合要求， 然后把 4 2 7 座位一个set
: 放到哈希表里
: 节点3 左边 1 2 5 右边 4 7 2 有重合 不符合要求， 然后把3 1 2 5 4 7作为 节点3
: 的set，
: 因为是post order所以可以保证 左右孩子都算完了再算父节点，
|
a*********4
发帖数: 7 | 15 a java solution:
import java.util.*;
public class FindNonDupeSubTree {
private class Node{
int val;
Node left;
Node right;
Node (int val){
this.val = val;
left = null;
right = null;
}
}
public boolean FindSubTree(Node root, Set nodeSet, ArrayList<
Integer> validTreeRoots){
if (root == null)
return true;
Set sleft = new HashSet();
Set sright = new HashSet();
boolean left = FindSubTree(root.left, sleft, validTreeRoots);
boolean right = FindSubTree(root.right, sright, validTreeRoots);
if (left && right){
// both are valid, let's check if left and right has any
overlaps.
for (Integer i : sleft){
if (sright.contains(i))
return false;
}
}
// now there's no overlap between left tree and right tree, check
root is in any of them or not
if (sleft.contains(root.val) || sright.contains(root.val))
return false;
// everything checked out as unique, merge root into all sets, and
add root to the validtreeroots
validTreeRoots.add(root.val);
nodeSet.addAll(sright);
nodeSet.addAll(sleft);
nodeSet.add(root.val);
return true;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
FindNonDupeSubTree ft = new FindNonDupeSubTree();
Node root = ft.new Node(3);
Node temp = null;
temp = ft.new Node(2);
root.left = temp;
temp = ft.new Node(4);
root.right = temp;
temp = ft.new Node(1);
root.left.left = temp;
temp = ft.new Node(5);
root.left.right = temp;
temp = ft.new Node(7);
root.right.left = temp;
temp = ft.new Node(2);
root.right.right = temp;
Set s = new HashSet();
ArrayList v = new ArrayList();
ft.FindSubTree(root, s, v);
System.out.println(v.size());
}
}
*>
【在 M*****M 的大作中提到】
: 类似找最大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);
|
s****n
发帖数: 220 | 16 the nodeset will remove the duplicated elements in the subtree, which will
affect the decision for the parent tree. |
s****n
发帖数: 220 | 17 the nodeset will remove the duplicated elements in the subtree, which will
affect the decision for the parent tree. |
a*********4
发帖数: 7 | 18 nodeset will remove dups, but that won't really impact the result. as long
as there's one copy of the presented nodes in the set, it will serve the
purpose of prevent dupe when comparing two sets. the result is stored in the
arraylist, which will maintain dup as is.
【在 s****n 的大作中提到】
: the nodeset will remove the duplicated elements in the subtree, which will
: affect the decision for the parent tree.
|
r*******k
发帖数: 1423 | 19 就是你这个方法，很好的
一点都不navie
set
3
【在 c********6 的大作中提到】
: 不是大牛，来个naive的方法吧：
: 后续遍历二叉树，
: 建一个哈希表 key是root节点，value是这颗树的所有节点的值 包括root，
: 没访问一个节点，看他左右子树哈希表值有没有重复，有的话就不符合，
: 然后再把左右子树的set merge 加上他自己作为这个节点的值放到哈希表里，
: 比如说 节点4 左边是 7 右边是 2 没有重合，符合要求， 然后把 4 2 7 座位一个set
: 放到哈希表里
: 节点3 左边 1 2 5 右边 4 7 2 有重合 不符合要求， 然后把3 1 2 5 4 7作为 节点3
: 的set，
: 因为是post order所以可以保证 左右孩子都算完了再算父节点，
|
f**********t
发帖数: 1001 | 20 bool UniqueBTrees(Node *root, vector &res, unordered_set &us) {
unordered_set lus;
unordered_set rus;
if ((!root->left || UniqueBTrees(root->left, res)) &&
(!root->right || UniqueBTrees(root->right, res)) &&
lus.find(root->val) == lus.end() &&
rus.find(root->val) == rus.end()) {
res.push_back(root);
for (int x : lus) {
us.insert(x);
}
for (int y : lus) {
us.insert(y);
}
us.insert(root->val);
return true;
} else {
return false;
}
} |
