[LeetCode] 863. All Nodes Distance K in Binary Tree

本文主要是介绍[LeetCode] 863. All Nodes Distance K in Binary Tree，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题：https://leetcode.com/problems/all-nodes-distance-k-in-binary-tree/

题目大意

求给树中，距给定结点指定长度的所有结点的val

思路

tree -> graph 、 bfs

先遍历树，并用map记录每个结点的父结点，将树变为图，然后 bfs。

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/
class Solution {Map<TreeNode,TreeNode> parentsMap =  new HashMap();void dfs(TreeNode root,TreeNode parentRoot){if(root == null)return ;parentsMap.put(root,parentRoot);dfs(root.left,root);dfs(root.right,root);    }public List<Integer> distanceK(TreeNode root, TreeNode target, int K) {dfs(root,null);Queue<TreeNode> queue = new LinkedList<>();queue.add(target);Set<TreeNode> hasVisitedNode = new HashSet();hasVisitedNode.add(target);while(!queue.isEmpty() && K-->0){int queueSize = queue.size();while(queueSize-- > 0){TreeNode curNode = queue.poll();TreeNode parentCurNOde = parentsMap.get(curNode);if(curNode.left!=null && !hasVisitedNode.contains(curNode.left)){queue.add(curNode.left);hasVisitedNode.add(curNode.left);}if(curNode.right!=null && !hasVisitedNode.contains(curNode.right)){queue.add(curNode.right);hasVisitedNode.add(curNode.right);}if(parentCurNOde!=null && !hasVisitedNode.contains(parentCurNOde)){queue.add(parentCurNOde);hasVisitedNode.add(parentCurNOde);}}}List<Integer> resList = new ArrayList<>();for(TreeNode node : queue){resList.add(node.val);}return resList;}
}

dfs + subTree_add

先用dfs 遍历树，这个dfs 的目的是查询每个节点到 target 的距离。
int dist 递归函数（dfs）：当前点到 target 的距离 + 1；（从上到下）

终止条件：dist(node) = -1 ，当 node == null；dist(node) == 1 ，当node == target。

递归转移方程：
dist(node) = dist(node.left) +1 或 dist(node.right) +1，由于只有一边会有target。
dist(node) == -1。若两边都为 -1

注意：dist 对于 target 的子树结点不会去求。

**void subTree_add(node,dist,K)：将从某点出发查找子树中到距离 target 为 K 的点；

int dist记录了当前结点到target 的距离。
dist == K，将该点作为答案。
若 dist > K ，停止在子树查找

有几种情况：

若该结点为空返回-1。
若该结点为target，那么使用 dfs 遍历深度，查询target子树中到target结点为K的节点。
若查看当前结点从左子树出发到 target的距离。若距离等于 K，将本结点添加。同时，查看从本结点的右结点的子树中到target 距离为K的节点。
右子树同理。

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/
class Solution {public void subTree_add(List<Integer> ans,TreeNode node,int dist,int K){if(node == null || dist>K)return;if(dist == K)ans.add(node.val);else{subTree_add(ans,node.left,dist + 1,K);subTree_add(ans,node.right,dist + 1,K);}}public int dist_dfs(List<Integer> ans,TreeNode node,TreeNode target,int K){if(node == null)return -1;if(node == target){subTree_add(ans,node,0,K);return 1;}int ldist = dist_dfs(ans,node.left,target,K);int rdist = dist_dfs(ans,node.right,target,K);if(ldist!=-1){if(ldist == K)ans.add(node.val);subTree_add(ans,node.right,ldist+1,K);return ldist+1;}else if(rdist!=-1){if(rdist == K)ans.add(node.val);subTree_add(ans,node.left,rdist+1,K);return rdist+1;}elsereturn -1;}public List<Integer> distanceK(TreeNode root, TreeNode target, int K) {List<Integer> ans = new ArrayList();dist_dfs(ans,root,target,K);return ans;}
}