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.
root tree given will be a TreeNode object.
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.
Input: root = , k = 1 Output: 1 Explanation: The nearest leaf node is the root node itself.
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.
rootrepresents a binary tree with at least
1node and at most
node.val == k.
Instead of a binary tree, if we converted the tree to a general graph, we could find the shortest path to a leaf using breadth-first search.\n
We use a depth-first search to record in our graph each edge travelled from parent to node.\n
After, we use a breadth-first search on nodes that started with a value of
k, so that we are visiting nodes in order of their distance to
k. When the node is a leaf (it has one outgoing edge, where the
root has a "ghost" edge to
null), it must be the answer.
Time Complexity: where is the number of nodes in the given input tree. We visit every node a constant number of times.\n
Space Complexity: , the size of the graph.\n
Intuition and Algorithm\n
Say from each node, we already knew where the closest leaf in it\'s subtree is. Using any kind of traversal plus memoization, we can remember this information.\n
Then the closest leaf to the target (in general, not just subtree) has to have a lowest common ancestor with the
target that is on the path from the
root to the
target. We can find the path from
target via any kind of traversal, and look at our annotation for each node on this path to determine all leaf candidates, choosing the best one.
Analysis written by: @awice.\n