leetcode863 二叉树中所有距离为k的点（树转图dfs）

快来打我* 2023-06-11 13:22 39阅读 0赞

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

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

示例 1：

输入：root = \[3,5,1,6,2,0,8,null,null,7,4\], target = 5, K = 2

输出：\[7,4,1\]

解释：  
所求结点为与目标结点（值为 5）距离为 2 的结点，  
值分别为 7，4，以及 1  
![在这里插入图片描述][format_png]

注意，输入的 “root” 和 “target” 实际上是树上的结点。  
上面的输入仅仅是对这些对象进行了序列化描述。

思路：  
树转图，以target节点为起点，搜索  
用Map<TreeNode,TreeNode> map，保存一个个点的指向(从当前节点指向父节点)  
Set set,来判断遍历否。  
然后，dfs以taget点开始，走target.left,target.right.以及target.parent.开始。

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        
    
        private Map<TreeNode,TreeNode> p = new HashMap<>();
        private Set<TreeNode> set = new HashSet<>();
        TreeNode targetNode;
        public List<Integer> distanceK(TreeNode root, TreeNode target, int K) {
        
            
            List<Integer> list = new ArrayList<>();
            find(root,null,target);
            dfs(list,K,targetNode);
            return list;
        }
    
        public void find(TreeNode root,TreeNode parent,TreeNode target)
        {
        
            if(root == null)
                return;
            if(root.val == target.val)
            {
        
                targetNode = root;
            }    
            p.put(root,parent);
            find(root.left,root,target);
            find(root.right,root,target);
        }
    
        public void dfs(List<Integer> list,int dis,TreeNode root){
             
            if(root == null|| set.contains(root))
                return;
             set.add(root);   
             if(dis<=0)
             {
        
                 list.add(root.val);
                 return;
             }   
    
            dfs(list,dis-1,root.left);
            dfs(list,dis-1,root.right);
            dfs(list,dis-1,p.get(root));
        }
    
       
    }

[format_png]: /images/20230531/57ed794323e84ca79442f3cdf9967862.png