Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/742.html

742. Closest Leaf in a Binary Tree

Level

Medium

Description

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.

Here, nearest to a leaf means the least number of edges travelled on the binary tree to reach any leaf of the tree. Also, a node is called a leaf if it has no children.

In the following examples, the input tree is represented in flattened form row by row. The actual root tree given will be a TreeNode object.

Example 1:

Input:
root = [1, 3, 2], k = 1
Diagram of binary tree:
          1
         / \
        3   2

Output: 2 (or 3)

Explanation: Either 2 or 3 is the nearest leaf node to the target of 1.

Example 2:

Input:
root = [1], k = 1
Output: 1

Explanation: The nearest leaf node is the root node itself.

Example 3:

Input:
root = [1,2,3,4,null,null,null,5,null,6], k = 2
Diagram of binary tree:
             1
            / \
           2   3
          /
         4
        /
       5
      /
     6

Output: 3
Explanation: The leaf node with value 3 (and not the leaf node with value 6) is nearest to the node with value 2.

Note:

  1. root represents a binary tree with at least 1 node and at most 1000 nodes.
  2. Every node has a unique node.val in range [1, 1000].
  3. There exists some node in the given binary tree for which node.val == k.

Solution

Use a map to store each node’s value and the path from the root to the node. For the root, the path is empty. For other nodes, use “0” to represent moving to the left child and use “1” to represent moving to the right child. Use a set to store all the leaf nodes’ values. Do breadth first search on the binary tree to obtain all nodes’ paths and obtain all the leaf nodes.

After all nodes’ paths are obtained and all the leaf nodes are obtained, for each leaf node, calculate the distance between the leaf node’s path and the target node’s path. The distance is calculated by obtaining the first index that the two paths differ, and calculate the sum of the remaining characters in both paths. Find the leaf node that has the least distance, and return its value.

  • /**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int findClosestLeaf(TreeNode root, int k) {
        Map<Integer, String> map = new HashMap<Integer, String>();
        map.put(root.val, "");
        Set<Integer> leaves = new HashSet<Integer>();
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            String path = map.getOrDefault(node.val, "");
            TreeNode left = node.left, right = node.right;
            if (left == null && right == null)
                leaves.add(node.val);
            else {
                if (left != null) {
                    String leftPath = path + "0";
                    map.put(left.val, leftPath);
                    queue.offer(left);
                }
                if (right != null) {
                    String rightPath = path + "1";
                    map.put(right.val, rightPath);
                    queue.offer(right);
                }
            }
        }
        String nodePath = map.getOrDefault(k, "");
        int leafVal = 0;
        int minDistance = Integer.MAX_VALUE;
        for (int leaf : leaves) {
            String leafPath = map.getOrDefault(leaf, "");
            int distance = distance(nodePath, leafPath);
            if (distance < minDistance) {
                leafVal = leaf;
                minDistance = distance;
            }
        }
        return leafVal;
    }

    public int distance(String path1, String path2) {
        int length1 = path1.length(), length2 = path2.length();
        int minLength = Math.min(length1, length2);
        int differentIndex = 0;
        while (differentIndex < minLength) {
            char c1 = path1.charAt(differentIndex), c2 = path2.charAt(differentIndex);
            if (c1 == c2)
                differentIndex++;
            else
                break;
        }
        int distance = length1 - differentIndex + length2 - differentIndex;
        return distance;
    }
}

  • Todo

  • # Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def findClosestLeaf(self, root: TreeNode, k: int) -> int:
        def dfs(root, p):
            if root:
                g[root].append(p)
                g[p].append(root)
                dfs(root.left, root)
                dfs(root.right, root)

        g = defaultdict(list)
        dfs(root, None)
        q = deque([node for node in g if node and node.val == k])
        seen = set()
        while q:
            node = q.popleft()
            seen.add(node)
            if node:
                if node.left is None and node.right is None:
                    return node.val
                for next in g[node]:
                    if next not in seen:
                        q.append(next)

All Problems

All Solutions