【LeetCode题解】2192. 有向无环图中一个节点的所有祖先+1026. 节点与其祖先之间的最大差值

文章目录

- [2192. 有向无环图中一个节点的所有祖先](https://leetcode.cn/problems/all-ancestors-of-a-node-in-a-directed-acyclic-graph/)
- - - - 思路：BFS+记忆化搜索
      - 代码：
      - 思路：逆向DFS
      - 代码：
- [1026. 节点与其祖先之间的最大差值](https://leetcode.cn/problems/maximum-difference-between-node-and-ancestor/)
- - - 思路：DFS
    - 代码：

2192. 有向无环图中一个节点的所有祖先

思路：BFS+记忆化搜索

1.遍历二维数组，构建邻接表g。统计每个结点的后续结点

2.g[i]表示结点i的所有后续结点

3.从小到大开始枚举i,i作为祖先结点

4.使用bfs搜索结点i的所有后续结点

5.布尔数组进行标记，避免重复统计

6.将枚举的结点i,添加到它的所有后续结点的祖先列表中

代码：

//2192. 有向无环图中一个节点的所有祖先 BFS
    private int n;
    private List<Integer>[] g;
    private List<List<Integer>> ans;

    public List<List<Integer>> getAncestors(int n, int[][] edges) {
        g = new List[n];
        this.n = n;
        Arrays.setAll(g,i->new ArrayList<>());
        for (int[]x:edges) {
            //遍历二维数组，构建邻接表g
             g[x[0]].add(x[1]);
             //g[i]表示结点i的所有后续结点
        }
        ans = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            ans.add(new ArrayList<>());
        }
        for (int i = 0; i < n; i++) {
            //从小到大开始枚举i,作为祖先结点
            bfs(i);
            //使用bfs搜索结点i的所有后续结点
            //然后把结点i,添加进它后续结点的祖先列表
        }
        return ans;
    }
    private void bfs(int s){
        Deque<Integer>deque = new ArrayDeque<>();
        deque.offer(s);
        boolean[] vis = new boolean[n];
        vis[s] = true;//进行标记，避免重复
        while (!deque.isEmpty()){
            int i = deque.poll();
            for (int j:g[i]) {
                if (!vis[j]){
                    vis[j] = true;
                    deque.offer(j);
                    ans.get(j).add(s);
                }
            }
        }
    }

思路：逆向DFS

1.将有向边进行翻转。

2.从i出发，能访问到的就是i的祖先

3.用数组标记避免重复访问

代码：

    public List<List<Integer>> getAncestors(int n, int[][] edges) {
        List<Integer>g[] = new ArrayList[n];
        Arrays.setAll(g,i->new ArrayList<>());
        for (int[]x:edges) {
            g[x[1]].add(x[0]);
            //反向建图
            //g[i]统计的是每个结点的祖先结点
        }
        List<List<Integer>> ans = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            ans.add(new ArrayList<>());
        }
        boolean[]vis = new boolean[n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(vis,false);
            //每次遍历进行重置
            dfsA(i,g,vis);
            vis[i] = false;//祖先结点不含本身
            for (int j = 0; j < n; j++) {
                if (vis[j]){
                    ans.get(i).add(j);
                }
            }
        }
        return ans;
    }
    private void dfsA(int x,List<Integer>[]g,boolean[]vis){
        vis[x] = true;//标记，避免重复统计
        for (int i:g[x]) {
            if (!vis[i]){
                dfsA(i,g,vis);
            }
        }
    }

1026. 节点与其祖先之间的最大差值

思路：DFS

1.进行深度优先遍历

2.每次都要维护当前结点与祖先结点最小值和最大值的差值

3.每次求出差值后，进行比较，更新最大差值

代码：

    private int num;
    public int maxAncestorDiff(TreeNode root) {
        dfsMax(root,root.val,root.val);
        //将root的值暂时为最大值和最小值
        return num;
    }
    private void dfsMax(TreeNode root ,int max,int min){
        if (root==null){
            //结点为空直接返回
            return ;
        }
        int x =Math.max(Math.abs(min-root.val),Math.abs(max-root.val));
        //求当前结点与祖先结点最小值和最大值的差值
        num = Math.max(x,num);
        //更新答案
        min = Math.min(min,root.val);
        //维护当前的最小值
        max = Math.max(max,root.val);
        //维护当前的最大值
        dfsMax(root.left,max,min);
        //在左树找
        dfsMax(root.right,max,min);
        //在右树找
    }