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:
rootrepresents a binary tree with at least1node and at most1000nodes.- Every node has a unique
node.valin range[1, 1000]. - 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; } } -
# 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) -
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: unordered_map<TreeNode*, vector<TreeNode*>> g; int findClosestLeaf(TreeNode* root, int k) { dfs(root, nullptr); queue<TreeNode*> q; for (auto& e : g) { if (e.first && e.first->val == k) { q.push(e.first); break; } } unordered_set<TreeNode*> seen; while (!q.empty()) { auto node = q.front(); q.pop(); seen.insert(node); if (node) { if (!node->left && !node->right) return node->val; for (auto next : g[node]) { if (!seen.count(next)) q.push(next); } } } return 0; } void dfs(TreeNode* root, TreeNode* p) { if (!root) return; g[root].push_back(p); g[p].push_back(root); dfs(root->left, root); dfs(root->right, root); } }; -
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func findClosestLeaf(root *TreeNode, k int) int { g := make(map[*TreeNode][]*TreeNode) var dfs func(root, p *TreeNode) dfs = func(root, p *TreeNode) { if root == nil { return } g[root] = append(g[root], p) g[p] = append(g[p], root) dfs(root.Left, root) dfs(root.Right, root) } dfs(root, nil) var q []*TreeNode for t, _ := range g { if t != nil && t.Val == k { q = append(q, t) break } } seen := make(map[*TreeNode]bool) for len(q) > 0 { node := q[0] q = q[1:] seen[node] = true if node != nil { if node.Left == nil && node.Right == nil { return node.Val } for _, next := range g[node] { if !seen[next] { q = append(q, next) } } } } return 0 }