FB 电面

刚刚结束的FB 电面
Problem 1: check if a BT is a BST
Problem 2: Given a set of Tree Nodes, find if they form a single valid BST, if so return the root
Example:
Nodes : (Node1, Node 2)
Tree structre:
   Nod

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

>补充内容 (2016-3-2 09:36):
代码贴在下面了，我后来自己又写了一遍，面试的时候只是说了思路，代码大体写了一下，bug遍地跑，目不忍睹呀 ! :) Bless 拿到onsite !

lotustree86 发表于 2016-3-2 11:37
你可以这么认为，输入是某一颗或者N颗树的节点组成的集合，顺序是乱的，但是每个节点还是保留原来左右子节 ...

这题首先可以判断有多少个node的indegree 为 0 吧。如果多于一个，肯定返回false.
如果只有一个，从这个节点出发做dfs构建二叉树，然后再判断是bst or not.

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. }
    

复制代码

import java.util.*;
import common.*;

public class Solution {
    public static TreeNode findRoot(Set<TreeNode> set, int count) {
        if(set.size() == 0) {
            return null;
        }

        // If there are only one TreeNode left, return it
        if(set.size() == 1) {
            return set.iterator().next();
        }

        // check if all TreeNodes are already visited, if so, return null
        if(count == 0) {
            return null;
        }

        // get any node that has not been visited yet
        Queue<TreeNode> queue = new ArrayDeque<>();
        for (TreeNode treeNode : set) {
            if(!treeNode.visited) {
                queue.offer(treeNode);
                break;
            }
        }
        
        // bfs traverse
        while(!queue.isEmpty()) {
            TreeNode node = queue.poll();
            node.visited = true;
            count--;

            if(node.left != null) {
                if(set.contains(node.left)) {
                    set.remove(node.left);
                    if(!node.left.visited) {
                        queue.offer(node.left);
                    }
                } else {
                    return null;
                }
            }

            if(node.right != null && !node.right.visited) {
                if(set.contains(node.right)) {
                    set.remove(node.right);
                    if(!node.right.visited) {
                        queue.offer(node.right);
                    }
                } else {
                    return null;
                }
            }
        }

        return findRoot(set, count);
    }
}

第二题，楼主 如果第一个找到的就是叶子节点，或者在遍历的时候，找到的一个节点，其下层的节点都被处理完了。怎么处理？判断是否合法的BST，应该判断节点及左右两个子节点是否满足BST的特性吧？对于找到的一个下层已被处理完的节点，这时只能找到他的父节点啊？

singku 发表于 2016-3-2 09:07
第二题，楼主 如果第一个找到的就是叶子节点，或者在遍历的时候，找到的一个节点，其下层的节点都被处理完 ...

我把代码贴出来了

第二题看不懂题意啊。。树的结构提前给定了嘛？

你可以这么认为，输入是某一颗或者N颗树的节点组成的集合，顺序是乱的，但是每个节点还是保留原来左右子节点的信息的，让你判断这些节点是不是来自同一颗二叉树，并且也不任何节点，并返还跟节点。

也不缺任何节点

我觉得可以做一个自底向上的广度收缩，看能不能找到一个符合BST条件的根节点。因为每个点的左右孩子都有，一遍遍历可以建立起每个节点的父子关系，丢到哈希表中，建立的时候如果有多个节点没有父节点，则返回false，否则这个节点是根节点。然后除根节点外的所有节点进入一个set. 对set中的每个节点，从哈西表中找到父节点，判断这三个或者两个节点是否满足BST特性。不满足，则函数返回false。满足则孩子出set. 当整个set中没有节点时，返回true. 自底向上的BST已经建好了。

duduhaha 发表于 2016-3-2 14:19
这题首先可以判断有多少个node的indegree 为 0 吧。如果多于一个，肯定返回false.
如果只有一个，从这个 ...

你这个方法不错，先找到根节点，再遍历