Closest Leaf in a Binary Tree

Given a binary tree where every node has a unique value, and a target key k.

Find the value of the nearest leaf node to target k in the tree. If there are multiple cases, you should follow these priorities:

1. The leaf node is in the left subtree of the node with k;

2. The leaf node is in the right subtree of the node with k;

3. The leaf node is not in the subtree of the node with k.

Input: {1, 3, 2}, k = 1
Output: 3
Explanation:
    1
   / \
  3   2

My Solutions:

首先用一个map储存所有节点的根节点。Time: O(N)

然后找到目标节点。这里需要用一个global value node储存目标节点。Time: O(N)

然后用一个q储存节点，先把node放进去，从这个节点开始遍历。建立一个set储存访问过的节点。Time: O(N)

• 如果q里弹出来的就是叶子节点，直接返回

• 如果不是，按照题目要求的先后顺序，bfs加入新的节点进入q

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */

public class Solution {
    /**
     * @param root: the root
     * @param k: an integer
     * @return: the value of the nearest leaf node to target k in the tree
     */
    TreeNode node; 
    public int findClosestLeaf(TreeNode root, int k) {
        Map<TreeNode, TreeNode> map = new HashMap<>();
        makeParentMap(root, map);
        node = null;
        findTargetNode(root, k);

        Queue<TreeNode> q = new LinkedList<>();
        q.add(node);
        Set<TreeNode> visited = new HashSet<>();
        while (!q.isEmpty()) {
            TreeNode n = q.poll();
            if (n.left == null && n.right == null) return n.val;
            visited.add(n);
            if (n.left != null && !visited.contains(n.left)) q.offer(n.left);
            if (n.right != null && !visited.contains(n.right)) q.offer(n.right);
            if (map.get(n) != null && !visited.contains(map.get(n))) q.add(map.get(n));
        }
        return -1;
    }

    private void makeParentMap(TreeNode root, Map<TreeNode, TreeNode> map) {
        if (root.left != null) {
            map.put(root.left, root);
            makeParentMap(root.left, map);
        }
        if (root.right != null) {
            map.put(root.right, root);
            makeParentMap(root.right, map);
        }
    }

    private void findTargetNode(TreeNode root, int k) {
        if (root == null) return;
        if (root.val == k) {
            node = root;
            return;
        }
        findTargetNode(root.left, k);
        findTargetNode(root.right, k);
    }
}