Given a tree,(binary tree possibily) every tree edge has a cost， find the least
cost or find the leaf node that the cost of path that from root to leaf is the
least.
Follow Up:
如果不是binary tree的结构，而是任意的DAG，问代码还是否work（yes）
有没有优化的地方？（用hashmap存下每个节点到叶节点的distance，这样再次访问到该叶节点就不必dfs下去）。
时间复杂度？优化之前是O(V!)优化之后是O(V+E)
BFS也要做些一下//我用DFS做，面试官说改成bfs优化一下，我就没弄出来
http://www.1point3acres.com/bbs/thread-230257-1-1.html

#include <iostream>
#include <queue>
#include <vector>
#include <stack>
#include <string>
#include <list>
#include <unordered_map>
#include <unordered_set>

using namespace std;
struct TreeNode {
    list<pair<int, TreeNode*>> children;
};
int getMinPath(TreeNode* root) {
    if (!root || !root->children.size()) return 0;    //!root!!!!!!!
    int res = INT_MAX;
    for (auto it = root->children.begin(); it != root->children.end(); it++)
        res = min(res, getMinPath((*it).second) + (*it).first);
    return res;
}
int getMinPathBFS(TreeNode* root) {
    if (!root) return 0;
    int res = INT_MAX;
    queue<pair<TreeNode*, int>> toVisit;
    toVisit.emplace(root, 0);
    while (!toVisit.empty()) {
        TreeNode* curr = toVisit.front().first;
        int dis = toVisit.front().second;
        toVisit.pop();
        if (!curr->children.size()) {
            res = min(res, dis);
            continue;
        }
        for (auto it = curr->children.begin(); it != curr->children.end(); it++)
            toVisit.emplace((*it).second, dis + (*it).first);
    }
    return res;
}
int main(int argc, char *argv[]) {
    TreeNode* n1 = new TreeNode();
    TreeNode* n2 = new TreeNode();
    TreeNode* n3 = new TreeNode();
    TreeNode* n4 = new TreeNode();
    TreeNode* n5 = new TreeNode();
    TreeNode* n6 = new TreeNode();
    TreeNode* n7 = new TreeNode();
    TreeNode* n8 = new TreeNode();
    TreeNode* n9 = new TreeNode();
    /*
    *       n1
    *    1 /  \ 3
    *     n2   n3
    *  2 /  \2  \6
    *   n4  n5   n6
    *  3/  9/ \5
    *  n7--n8  n9
    */
    n1->children.emplace_back(1, n2);
    n1->children.emplace_back(3, n3);
    n2->children.emplace_back(2, n4);
    n2->children.emplace_back(2, n5);
    n3->children.emplace_back(6, n6);
    n4->children.emplace_back(3, n7);
    n5->children.emplace_back(9, n8);
    n5->children.emplace_back(5, n9);

    cout<<getMinPath(n1)<<endl;
    cout<<getMinPathBFS(n1)<<endl;

    n5->children.emplace_back(4, n6);
    n7->children.emplace_back(2, n8);


    cout<<getMinPath(n1)<<endl;
    cout<<getMinPathBFS(n1)<<endl;



}