863. 二叉树中所有距离为 K 的结点

青旅半醒 2022-08-31 07:09 120阅读 0赞

给定一个二叉树（具有根结点 root）， 一个目标结点 target ，和一个整数值 K 。

返回到目标结点 target 距离为 K 的所有结点的值的列表。 答案可以以任何顺序返回。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQzNDkwMg_size_16_color_FFFFFF_t_70][]

class Solution {
    
        // 用map记录每个节点的父节点
        private Map<TreeNode, TreeNode> parents = new HashMap<>();
    
        private Set<TreeNode> used = new HashSet<>();
    
        private TreeNode targetNode;
    
        List<Integer> res = new LinkedList<>();
        public List<Integer> distanceK(TreeNode root, TreeNode target, int K) {
            find(root, null, target);
           
            dfs(targetNode,  K);
            return res;
        }
    
        private void find(TreeNode root, TreeNode parent, TreeNode target) {
            if (null == root) {
                return;
            }
            if (root.val == target.val) {
                targetNode = root;
            }
            parents.put(root, parent);
            find(root.left, root, target);
            find(root.right, root, target);
        }
        // 找到目标节点后以目标节点为开始位置向三个方向蔓延
        private void dfs(TreeNode root,  int distance) {
            if (root != null && !used.contains(root)) {
                // 标记为已访问
                used.add(root);
                if (distance <= 0) {
                    res.add(root.val);
                    return;
                }
                dfs(root.left,  distance - 1);
                dfs(root.right,  distance - 1);
                dfs(parents.get(root), distance - 1);
            }
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQzNDkwMg_size_16_color_FFFFFF_t_70]: /images/20220829/df312391901a43a88a2d03b8a1d4302f.png