FB 电面

楼主为什么要用count呢？还是说给定的参数就有count？求检查下我的代码：

1. public TreeNode findSingleBST(Set<TreeNode> set) {
   
2.     if (set == null) {
   
3.         return null;
   
4.     }
   
5. 
   
6.     TreeNode root = null;
   
7.     for (TreeNode node : new HashSet<>(set)) {
   
8.         if (set.contains(node)) {
   
9.             root = node;
   
10.             // dfs
    
11.             Stack<TreeNode> stack = new Stack<>();
    
12.             stack.push(root);
    
13.             while (!stack.isEmpty()) {
    
14.                 TreeNode current = stack.pop();
    
15.                 if (current != root) {
    
16.                     set.remove(current);
    
17.                 }
    
18.                 if (current.left != null) {
    
19.                     stack.push(current.left);
    
20.                 }
    
21.                 if (current.right != null) {
    
22.                     stack.push(current.right);
    
23.                 }
    
24.             }
    
25.         }
    
26.     }
    
27. 
    
28.     if (set.size() > 1) {
    
29.         return null;
    
30.     }
    
31.     return root;
    
32. }

复制代码

lotustree86 发表于 2016-3-2 15:24
你这个方法不错，先找到根节点，再遍历

1. public class Solution {
   
2.   public TreeNode onetree(Set<TreeNode> set) {
   
3.     Set<TreeNode> candidate = new HashSet<>(set);
   
4.     for (TreeNode tn : set) {
   
5.       if (tn.left != null) {
   
6.         candidate.remove(tn.left);
   
7.       }
   
8.       if (tn.right != null) {
   
9.         candidate.remove(tn.right);
   
10.       }
    
11.     }
    
12.     for (TreeNode root : candidate) {
    
13.       Set<TreeNode> nodes = new HashSet<>(set);
    
14.       Deque<TreeNode> queue = new ArrayDeque<>();
    
15.       queue.offer(root);
    
16.       nodes.remove(root);
    
17.       while (!queue.isEmpty()) {
    
18.         TreeNode tn = queue.poll();
    
19.         if (tn.left != null) {
    
20.           queue.offer(tn.left);
    
21.           nodes.remove(tn.left);
    
22.         }
    
23.         if (tn.right != null) {
    
24.           queue.offer(tn.right);
    
25.           nodes.remove(tn.right);
    
26.         }
    
27.       }
    
28.       if (nodes.isEmpty())
    
29.         return root;
    
30.     }
    
31.     return null;
    
32.   }
    
33. 
    
34.   public static void main(String[] args) {
    
35.     Solution s = new Solution();
    
36.     TreeNode tn1 = new TreeNode(1);
    
37.     TreeNode tn2 = new TreeNode(2);
    
38.     TreeNode tn3 = new TreeNode(3);
    
39.     TreeNode tn4 = new TreeNode(4);
    
40.     TreeNode tn5 = new TreeNode(5);
    
41.     TreeNode tn6 = new TreeNode(6);
    
42.     TreeNode tn7 = new TreeNode(7);
    
43.     tn1.left = tn2;
    
44.     tn1.right = tn3;
    
45.     tn2.right = tn4;
    
46.     tn5.left = tn6;
    
47.     tn5.right = tn7;
    
48.     Set<TreeNode> set1 = new HashSet<>();
    
49.     set1.add(tn1);
    
50.     set1.add(tn2);
    
51.     set1.add(tn3);
    
52.     set1.add(tn4);
    
53.     Set<TreeNode> set2 = new HashSet<>();
    
54.     set2.add(tn1);
    
55.     set2.add(tn2);
    
56.     set2.add(tn3);
    
57.     set2.add(tn4);
    
58.     set2.add(tn5);
    
59.     set2.add(tn6);
    
60.     set2.add(tn7);
    
61.     System.out.println(s.onetree(set1).equals(tn1));
    
62.     System.out.println(s.onetree(set2) == null);
    
63.   }
    
64. }
    

复制代码

tldxk 发表于 2016-3-12 10:26
楼主为什么要用count呢？还是说给定的参数就有count？求检查下我的代码：

请问楼上做法，这个没有判断是否为BST吧？包括大家的做法，都没看出在哪里判断是BST了。抱歉，求讲解！

第二题应该用拓扑排序的思想。