九章算法 | Twitter 面试题：Tree

撰文 | JZ
专栏 | 九章算法

题目描述

给出两个list x，y，代表x[i]与y[i]之间有一条边，整个边集构成一棵树，1为根。现在有个list a,b，表示询问节点a[i]与b[i]是什么关系，如果a[i]与b[i]是兄弟，即有同一个父节点，输出1，如果a[i]与b[i]是父子关系，输出2，否则输出0。

思路点拨

一次dfs将树的每个节点的father处理出来，并保存每个节点的儿子。

考点分析

本题考察了树遍历，一次树遍历就能将每个节点的father处理出来，然后对每个节点维护一个map，这个map存下所有的儿子，那么判断是否是兄弟关系，就判断father是否相同，父子关系就用map判断。

九章参考程序

http://www. jiuzhang.com/solution/t ree/

        /**
* 本参考程序来自九章算法，由 @斌助教 提供。版权所有，转发请注明出处。
* - 九章算法致力于帮助更多中国人找到好的工作，教师团队均来自硅谷和国内的一线大公司在职工程师。
* - 现有的面试培训课程包括：九章算法班，系统设计班，算法强化班，Java入门与基础算法班，Android 项目实战班，
* - Big Data 项目实战班，算法面试高频题班, 动态规划专题班
* - 更多详情请见官方网站：http://www.jiuzhang.com/?source=code
*/ 

public class Solution {
    /**
     * @param x: The x
     * @param y: The y
     * @param a: The a
     * @param b: The b
     * @return: The Answer
     */
     
    void dfs(int x, int fa, List<List<Integer>>g, List<Map<Integer, Integer>>mp, int[] f) {
        f[x] = fa;
        for(int i = 0; i < g.get(x).size(); i++) {
            int y = g.get(x).get(i);
            if(y != fa) {
                mp.get(x).put(y, 1);
                dfs(y, x, g, mp, f);
            }
        }
    }
     
    public int[] tree(int[] x, int[] y, int[] a, int[] b) {
        // Write your code here
        List<List<Integer>>g = new ArrayList<List<Integer>>();
        List<Map<Integer, Integer>> mp = new ArrayList<Map<Integer, Integer>>();
        int[] f = new int[100005];
        int[] ans = new int[a.length];
        for(int i = 0; i < 100005; i++) {
            mp.add(new HashMap<Integer, Integer>());
        }
        for(int i = 0; i < x.length + 2; i++) {
            g.add(new ArrayList<Integer>());
        }
        for(int i = 0; i < x.length; i++) {
            g.get(x[i]).add(y[i]);
            g.get(y[i]).add(x[i]);
        }
        dfs(1, 0, g, mp, f);
        for(int i = 0; i < a.length; i++) {
            if(f[a[i]] == f[b[i]]) {
                ans[i] = 1;
            } else if(mp.get(a[i]).containsKey(b[i]) || mp.get(b[i]).containsKey(a[i])) {
                ans[i] = 2;
            } else {
                ans[i] = 0;
            }
        }
        return ans;
    }
}