# 0742. Closest Leaf in a Binary Tree
###### tags: `Leetcode` `Medium` `FaceBook` `BFS` `DFS`
Link: https://leetcode.com/problems/closest-leaf-in-a-binary-tree/
## 思路
### 思路一
先dfs一次 找到targetNode还有用map记录parent
再bfs找到nearest leafnode
### 思路二
跑的没有思路一快 但是可以提供一个思路
dfs记录所有的点到root的长度并且找到target
遍历所有点 如果是leaf node，就看它和target之间的距离
求的方法是用先找到它和target的lca，它到root的距离+target到root的距离-2*lca到root的距离就是它和target之间的距离

**Tree上两点a和b之间的距离求法：dfs找到这两个点，并且记录所有点到root的距离，算他们的lca，a到root的距离+b到root的距离-2*lca到root的距离就是答案**
## Code
### 思路一

class Solution {
    public int findClosestLeaf(TreeNode root, int k) {
        Map<TreeNode, TreeNode> parent = new HashMap<>();
        TreeNode target = null;
        Stack<TreeNode> stack = new Stack<>();
        stack.add(root);
        while(!stack.isEmpty()){
            TreeNode curr = stack.pop();
            if(curr.val == k) target = curr;
            if(curr.left!=null){
                parent.put(curr.left, curr);
                stack.add(curr.left);
            }
            if(curr.right!=null){
                parent.put(curr.right, curr);
                stack.add(curr.right);
            }
        }
        
        Set<TreeNode> visited = new HashSet<>();
        Queue<TreeNode> q = new LinkedList<>();
        q.add(target);
        while(!q.isEmpty()){
            TreeNode curr = q.poll();
            if(curr.left==null && curr.right==null) return curr.val;
            if(visited.contains(curr)) continue;
            visited.add(curr);
            if(curr.left!=null) q.add(curr.left);
            if(curr.right!=null) q.add(curr.right);
            if(parent.containsKey(curr)) q.add(parent.get(curr));
        }
        return k;
    }
}

### 思路二

class Solution {
    Map<TreeNode, Integer> map;
    TreeNode target;
    int targetVal;
    public int findClosestLeaf(TreeNode root, int k) {
        map = new HashMap<>();
        target = null;
        targetVal = k;
        distanceToRoot(root, 0);
        
        int shortestDist = Integer.MAX_VALUE;
        int shortestVal = 0;
        
        for(TreeNode curr:map.keySet()){
            if(curr.left==null && curr.right==null){
                TreeNode lca = findLCA(root, curr, target);
                int dist = map.get(curr)+map.get(target)-2*map.get(lca);
                if(dist<shortestDist){
                    shortestDist = dist;
                    shortestVal = curr.val;
                }
            }
        }
        return shortestVal;
    }
    
    private void distanceToRoot(TreeNode root, int distance){
        if(root == null) return;
        if(root.val == targetVal) target = root;
        map.put(root, distance);
        distanceToRoot(root.left, distance+1);
        distanceToRoot(root.right, distance+1);
    }
    
    private TreeNode findLCA(TreeNode root, TreeNode p, TreeNode q){
        if(root==null || root==p || root==q) return root;
        TreeNode left = findLCA(root.left, p, q);
        TreeNode right = findLCA(root.right, p, q);
        if(left!=null && right!=null) return root;
        if(left!=null) return left;
        else return right;
    }
    
}