http://bookshadow.com/weblog/2017/12/10/leetcode-closest-leaf-in-a-binary-tree/
Given a binary tree where every node has a unique value, and a target key
k
, find the closest leaf node to target k
in the tree.
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.
Note:
root
represents a binary tree with at least1
node and at most1000
nodes.- Every node has a unique
node.val
in range[1, 1000]
. - There exists some node in the given binary tree for which
node.val == k
.
问题转换为在无向/等权重的图中找一条从起始节点到任意叶子节点最短路径。
int answer;
public int findClosest(TreeNode root, int key) {
answer = Integer.MAX_VALUE;
helper(root, key, new ArrayList<TreeNode>());
return answer;
}
private void helper(TreeNode node, int key, List<TreeNode> path) {
if (node == null) {
return;
} else if (node.val != key) {
path.add(node);
helper(node.left, key, path);
helper(node.right, key, path);
path.remove(path.size() - 1);
} else {
// key matches with current node value
answer = lenToLowerLeaf(node);
// answer initially = cloest leaf from lower
int len = path.size();
for (int i = 0; i < len; i++) {
// for every ancestor, calculate distance and compare
int ithToLowerLeaf = lenToLowerLeaf(path.get(i));
answer = Math.min(answer, (len - i) + ithToLowerLeaf);
}
}
}
private int lenToLowerLeaf(TreeNode node) {
if (node == null) {
return Integer.MAX_VALUE;
} else if (node.left == null && node.right == null) {
return 0;
} else {
return 1 + Math.min(lenToLowerLeaf(node.left), lenToLowerLeaf(node.right));
}
}
X. Videos
花花酱 LeetCode 742. Closest Leaf in a Binary Tree - 刷题找工作 EP131