题目来源

力扣每日一题；题序：2385

我的题解

方法一 转化为图+广度优先搜索

先将树转换为图，然后进行广度优先搜索进行感染模拟

时间复杂度：O(n)
空间复杂度：O(n)

java">class Solution {int size=0;public int amountOfTime(TreeNode root, int start) {// List<Integer>[] g=createGraph(root);Map<Integer,List<Integer>> map=createMap(root);// System.out.println(map);Set<Integer> set=new HashSet<>();set.add(start);Queue<Integer> queue=new LinkedList<>();queue.offer(start);int res=0;while(!queue.isEmpty()){int sz=queue.size();for(int i=0;i<sz;i++){List<Integer> t=map.get(queue.poll());if(t==null)continue;for(Integer e:t){if(set.add(e))queue.offer(e);}}res++;}//最后一层会多计算一次return res-1;}public Map<Integer,List<Integer>> createMap(TreeNode root){Queue<TreeNode> queue=new LinkedList<>();queue.offer(root);Map<Integer,List<Integer>> map=new HashMap<>();while(!queue.isEmpty()){int sz=queue.size();for(int i=0;i<sz;i++){TreeNode tree=queue.poll();int t=tree.val;if(tree.left!=null){addEdge(t,tree.left.val,map);queue.offer(tree.left);}if(tree.right!=null){addEdge(t,tree.right.val,map);queue.offer(tree.right);}}size+=sz;}return map;}public void addEdge(int from,int to ,Map<Integer,List<Integer>> map){List<Integer> l1=map.getOrDefault(from,new ArrayList<>());List<Integer> l2=map.getOrDefault(to,new ArrayList<>());l1.add(to);l2.add(from);map.put(from,l1);map.put(to,l2);}
}

方法二 记录父节点+DFS

参考灵神的代码
首先从 root出发 DFS 这棵树，找到节点值为 start 的节点 startNode。DFS 的同时，用一个哈希表（或者数组）记录每个节点的父节点。
然后从 startNode出发 DFS 这棵树，求出二叉树的最大深度，即为答案（把 startNode 的深度当作 0）。注意除了递归左右儿子以外，还需要递归父节点。为避免重复访问节点，可以添加一个递归参数 from，表示当前节点是从节点 from 过来的，不去重复访问节点 from。

时间复杂度：O(n)
空间复杂度：O(n)

java">class Solution {private TreeNode startNode;private final Map<TreeNode, TreeNode> fa = new HashMap<>();public int amountOfTime(TreeNode root, int start) {dfs(root, null, start);return maxDepth(startNode, startNode);}private void dfs(TreeNode node, TreeNode from, int start) {if (node == null) {return;}fa.put(node, from); // 记录每个节点的父节点if (node.val == start) {startNode = node; // 找到 start}dfs(node.left, node, start);dfs(node.right, node, start);}private int maxDepth(TreeNode node, TreeNode from) {if (node == null) {return -1; // 注意这里是 -1，因为 start 的深度为 0}int res = -1;if (node.left != from) {res = Math.max(res, maxDepth(node.left, node));}if (node.right != from) {res = Math.max(res, maxDepth(node.right, node));}if (fa.get(node) != from) {res = Math.max(res, maxDepth(fa.get(node), node));}return res + 1;}
}

方法三 一次遍历+树的直径

参考灵神的代码
实质就是求 以start为直径端点的树的直径

时间复杂度：O(n)
空间复杂度：O(n)

java">class Solution {private int ans;public int amountOfTime(TreeNode root, int start) {dfs(root, start);return ans;}private int[] dfs(TreeNode node, int start) {if (node == null) {return new int[]{0, 0};}int[] leftRes = dfs(node.left, start);int[] rightRes = dfs(node.right, start);int lLen = leftRes[0], lFound = leftRes[1];int rLen = rightRes[0], rFound = rightRes[1];if (node.val == start) {// 计算子树 start 的最大深度// 注意这里和方法一的区别，max 后面没有 +1，所以算出的也是最大深度ans = Math.max(lLen, rLen);return new int[]{1, 1}; // 找到了 start}if (lFound == 1 || rFound == 1) {// 只有在左子树或右子树包含 start 时，才能更新答案ans = Math.max(ans, lLen + rLen); // 两条链拼成直径// 保证 start 是直径端点return new int[]{(lFound == 1 ? lLen : rLen) + 1, 1};}return new int[]{Math.max(lLen, rLen) + 1, 0};}
}

灵神是真的强！！！！！！！！！！

有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈😄~