阿里一面凉凉....

我看别人的面经都是上来问题目...我这直接给了两道算法题....一个小时都没写出来.....

并且由于没有实习....面试官还直言先实习比较好....

忘记那个部门的了...我发了三分简历给不同的人

1、计算多叉树中最长连续序列的长度（LC549，付费题目）

public class LC549 {

    int max = 0;

    public int longestConsecutive(Multi_TreeNode root) {
        longestPath(root);
        return max;
    }

    public int[] longestPath(Multi_TreeNode node) {
        if (node == null)
            return new int[]{0, 0};
        int up = 1, down = 1;
        List<Multi_TreeNode> cs = node.childs;
        for (Multi_TreeNode c : cs) {
            if (c != null) {
                int[] l = longestPath(c);
                if (node.val == c.val + 1)
                    down = Math.max(l[1] + 1, down);
                else if (node.val == c.val - 1)
                    up = Math.max(l[0] + 1, up);
            }
        }
        max = Math.max(max, down + up - 1);
        return new int[]{up, down};
    }
}

class Multi_TreeNode {

    int val;
    List<Multi_TreeNode> childs;

    public Multi_TreeNode(int val) {
        this.val = val;
        childs = new ArrayList<>();
    }
}

2、二叉树在x轴上的投影（LC314，垂直遍历，也是付费题目）

public class LC314 {
    //测试
    public static void main(String args[]) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(7);

        List<List<Integer>> list = new LC314().verticalOrder(root);
        int[] res = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            res[i] = list.get(i).get(0);
        }
        System.out.println(Arrays.toString(res));
    }


    /**
     * 存储在x轴上距离root的最大/小距离
     */
    int[] len = new int[2];

    /**
     * 总的结果
     */
    List<List<Integer>> res = new ArrayList<>();

    /**
     * 每一列的遍历结果
     */
    List<Integer> vertical = new ArrayList<>();

    /**
     * 垂直遍历
     * @param root  根节点
     */
    public List<List<Integer>> verticalOrder(TreeNode root) {
        getMinAndMax(root, 0);
        for (int i = len[0]; i <= len[1]; i++) {
            dfs(root, i, 0);
            res.add(new ArrayList<>(vertical));
            vertical.clear();
        }
        return res;
    }

    /**
     * 计算在x轴上距离root的最大/小距离（记水平为x轴）
     *
     * @param root 根节点
     * @param u    当前节点距离root的垂直距离
     */
    public void getMinAndMax(TreeNode root, int u) {
        if (root == null) return;
        if (len[0] > u) len[0] = u;
        else if (len[1] < u) len[1] = u;

        getMinAndMax(root.left, u - 1);
        getMinAndMax(root.right, u + 1);
    }

    /**
     *
     * @param node  当前节点
     * @param u     node距离root的距离
     * @param n     当前节点距离node的距离
     */
    private void dfs(TreeNode node, int u, int n) {
        if (node == null) return;
        if (u == n) vertical.add(node.val);
        dfs(node.left, u, n - 1);
        dfs(node.right, u, n + 1);
    }

}