花花酱 LeetCode 742. Closest Leaf in a Binary Tree

Problem:

Given a binary tree where every node has a unique value, and a target key k, find the value of the closest leaf node to target k in the tree.

Here, closest 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:

Example 2:

Example 3:

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.

题目大意:

给你一棵树，每个节点的值都不相同。

给定一个节点值，让你找到离这个节点距离最近的叶子节点的值。

Idea:

Shortest path from source to any leaf nodes in a undirected unweighted graph.

问题转换为在无向/等权重的图中找一条从起始节点到任意叶子节点最短路径。

Solution:

C++ / DFS + BFS

Time complexity: O(n)

Space complexity: O(n)