LeetCode 742 - Closest Leaf in a Binary Tree

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 roottree given will be a TreeNode object.

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 closest 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.

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

int findClosestLeaf(TreeNode* root, int k) {         graph_.clear();         start_ = nullptr;         buildGraph(root, nullptr, k);         queue<TreeNode*> q;         q.push(start_);         unordered_set<TreeNode*> seen;         while (!q.empty()) {             int size = q.size();             while (size-->0) {                 TreeNode* curr = q.front();                 q.pop();                                 seen.insert(curr);                                 if (!curr->left && !curr->right) return curr->val;                 for (TreeNode* node : graph_[curr])                     if (!seen.count(node)) q.push(node);             }         }         return 0;     } private:     void buildGraph(TreeNode* node, TreeNode* parent, int k) {         if (!node) return;         if (node->val == k) start_ = node;         if (parent) {             graph_[node].push_back(parent);             graph_[parent].push_back(node);         }         buildGraph(node->left, node, k);         buildGraph(node->right, node, k);     }          unordered_map<TreeNode*, vector<TreeNode*>> graph_;     TreeNode* start_; };

http://www.shuati123.com/blog/2015/10/07/closest-leaf-binary-tree/

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