# LeetCode Number of Good Leaf Nodes Pairs

5474. Number of Good Leaf Nodes Pairs

Given the root of a binary tree and an integer distance. A pair of two different leaf nodes of a binary tree is said to be good if the length of the shortest path between them is less than or equal to distance.

Return the number of good leaf node pairs in the tree.

Example 1:

Input: root = [1,2,3,null,4], distance = 3
Output: 1
Explanation: The leaf nodes of the tree are 3 and 4 and the length of the shortest path between them is 3. This is the only good pair.


Example 2:

Input: root = [1,2,3,4,5,6,7], distance = 3
Output: 2
Explanation: The good pairs are [4,5] and [6,7] with shortest path = 2. The pair [4,6] is not good because the length of ther shortest path between them is 4.


Example 3:

Input: root = [7,1,4,6,null,5,3,null,null,null,null,null,2], distance = 3
Output: 1
Explanation: The only good pair is [2,5].


Example 4:

Input: root = [100], distance = 1
Output: 0


Example 5:

Input: root = [1,1,1], distance = 2
Output: 1


Constraints:

• The number of nodes in the tree is in the range [1, 2^10].
• Each node’s value is between [1, 100].
• 1 <= distance <= 10

class Solution {
private:
void CollectLeaves(TreeNode *root, unordered_map<TreeNode*, vector<TreeNode*>> &all_paths, vector<TreeNode*> &one_path) {
if (root == NULL)return;
one_path.push_back(root);
if (root->left == NULL && root->right == NULL) {
all_paths[root] = one_path;
}
else {
CollectLeaves(root->left, all_paths, one_path);
CollectLeaves(root->right, all_paths, one_path);
}
one_path.pop_back();
}
int CalDist(vector<TreeNode*> &path1, vector<TreeNode*> &path2) {
int m = path1.size(), n = path2.size();
int i = 0;
while (i < m&&i < n) {
if (path1[i] != path2[i])break;
++i;
}
return (m - i) + (n - i);
}

public:
int countPairs(TreeNode* root, int distance) {
unordered_map<TreeNode*, vector<TreeNode*>> all_paths;
vector<TreeNode*> one_path;
CollectLeaves(root, all_paths, one_path);
vector<TreeNode*> leaves;
for (unordered_map<TreeNode*, vector<TreeNode*>>::iterator it = all_paths.begin(); it != all_paths.end(); ++it) {
leaves.push_back(it->first);
}

int ans = 0;
for (int i = 0; i < leaves.size(); ++i) {
for (int j = i + 1; j < leaves.size(); ++j) {
int d = CalDist(all_paths[leaves[i]], all_paths[leaves[j]]);
if (d <= distance)++ans;
}
}

return ans;
}
};

# LeetCode Lowest Common Ancestor of a Binary Tree

LeetCode Lowest Common Ancestor of a Binary Tree Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree. According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

        _______3______
/              \
___5__          ___1__
/      \        /      \
6      _2       0       8
/  \
7   4

For example, the lowest common ancestor (LCA) of nodes 5 and 1 is 3. Another example is LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

# LeetCode Lowest Common Ancestor of a Binary Search Tree

235. Lowest Common Ancestor of a Binary Search Tree

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Given binary search tree:  root = [6,2,8,0,4,7,9,null,null,3,5]

Example 1:

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Explanation: The LCA of nodes 2 and 8 is 6.


Example 2:

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
Output: 2
Explanation: The LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.


Note:

• All of the nodes’ values will be unique.
• p and q are different and both values will exist in the BST.

class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)
{
if (p->val > q->val)
swap(p, q);
if (p->val <= root->val && q->val >= root->val)
return root;
if (p->val < root->val && q->val < root->val)
return lowestCommonAncestor(root->left, p, q);
if (p->val > root->val && q->val > root->val)
return lowestCommonAncestor(root->right, p, q);
}
};

class Solution {
void BSTSearch(TreeNode* root, TreeNode* p, vector<TreeNode*>& ancestors) {
while (root->val != p->val) {
ancestors.push_back(root);
if (p->val > root->val)root = root->right;
else root = root->left;
}
ancestors.push_back(root);
}
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
vector<TreeNode*> pa, qa;
BSTSearch(root, p, pa);
BSTSearch(root, q, qa);
int i = 0;
for (; i < pa.size() && i < qa.size(); ++i) {
if (pa[i] != qa[i])break;
}
return pa[i - 1];
}
};

# hihoCoder 1069-最近公共祖先·三

hihoCoder 1069-最近公共祖先·三 #1069 : 最近公共祖先·三 时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 上上回说到，小Hi和小Ho使用了Tarjan算法来优化了他们的“最近公共祖先”网站，但是很快这样一个离线算法就出现了问题：如果只有一个人提出了询问，那么小Hi和小Ho很难决定到底是针对这个询问就直接进行计算还是等待一定数量的询问一起计算。毕竟无论是一个询问还是很多个询问，使用离线算法都是只需要做一次深度优先搜索就可以了的。 那么问题就来了，如果每次计算都只针对一个询问进行的话，那么这样的算法事实上还不如使用最开始的朴素算法呢！但是如果每次要等上很多人一起的话，因为说不准什么时候才能够凑够人——所以事实上有可能要等上很久很久才能够进行一次计算，实际上也是很慢的！ “那到底要怎么办呢？在等到10分钟，或者凑够一定数量的人两个条件满足一个时就进行运算？”小Ho想出了一个折衷的办法。 “哪有这么麻烦！别忘了和离线算法相对应的可是有一个叫做在线算法的东西呢！”小Hi笑道。 小Ho面临的问题还是和之前一样：假设现在小Ho现在知道了N对父子关系——父亲和儿子的名字，并且这N对父子关系中涉及的所有人都拥有一个共同的祖先（这个祖先出现在这N对父子关系中），他需要对于小Hi的若干次提问——每次提问为两个人的名字（这两个人的名字在之前的父子关系中出现过），告诉小Hi这两个人的所有共同祖先中辈分最低的一个是谁？ 提示：最近公共祖先无非就是两点连通路径上高度最小的点嘛！ 输入 每个测试点（输入文件）有且仅有一组测试数据。 每组测试数据的第1行为一个整数N，意义如前文所述。 每组测试数据的第2~N+1行，每行分别描述一对父子关系，其中第i+1行为两个由大小写字母组成的字符串Father_i, Son_i，分别表示父亲的名字和儿子的名字。 每组测试数据的第N+2行为一个整数M，表示小Hi总共询问的次数。 每组测试数据的第N+3~N+M+2行，每行分别描述一个询问，其中第N+i+2行为两个由大小写字母组成的字符串Name1_i, Name2_i，分别表示小Hi询问中的两个名字。 对于100%的数据，满足N<=10^5，M<=10^5, 且数据中所有涉及的人物中不存在两个名字相同的人（即姓名唯一的确定了一个人），所有询问中出现过的名字均在之前所描述的N对父子关系中出现过，且每个输入文件中第一个出现的名字所确定的人是其他所有人的公共祖先。 输出 对于每组测试数据，对于每个小Hi的询问，按照在输入中出现的顺序，各输出一行，表示查询的结果：他们的所有共同祖先中辈分最低的一个人的名字。 样例输入 4 Adam Sam Sam Joey Sam Micheal Adam Kevin 3 Sam Sam Adam Sam Micheal Kevin 样例输出 Sam Adam Adam

# POJ 1330-Nearest Common Ancestors

POJ 1330-Nearest Common Ancestors Nearest Common Ancestors Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 19432 Accepted: 10292 Description A rooted tree is a well-known data structure in computer science and engineering. An example is shown below: In the figure, each node is labeled with an integer from {1, 2,…,16}. Node 8 is the root of the tree. Node x is an ancestor of node y if node x is in the path between the root and node y. For example, node 4 is an ancestor of node 16. Node 10 is also an ancestor of node 16. As a matter of fact, nodes 8, 4, 10, and 16 are the ancestors of node 16. Remember that a node is an ancestor of itself. Nodes 8, 4, 6, and 7 are the ancestors of node 7. A node x is called a common ancestor of two different nodes y and z if node x is an ancestor of node y and an ancestor of node z. Thus, nodes 8 and 4 are the common ancestors of nodes 16 and 7. A node x is called the nearest common ancestor of nodes y and z if x is a common ancestor of y and z and nearest to y and z among their common ancestors. Hence, the nearest common ancestor of nodes 16 and 7 is node 4. Node 4 is nearer to nodes 16 and 7 than node 8 is. For other examples, the nearest common ancestor of nodes 2 and 3 is node 10, the nearest common ancestor of nodes 6 and 13 is node 8, and the nearest common ancestor of nodes 4 and 12 is node 4. In the last example, if y is an ancestor of z, then the nearest common ancestor of y and z is y. Write a program that finds the nearest common ancestor of two distinct nodes in a tree. Input The input consists of T test cases. The number of test cases (T) is given in the first line of the input file. Each test case starts with a line containing an integer N , the number of nodes in a tree, 2<=N<=10,000. The nodes are labeled with integers 1, 2,…, N. Each of the next N -1 lines contains a pair of integers that represent an edge –the first integer is the parent node of the second integer. Note that a tree with N nodes has exactly N – 1 edges. The last line of each test case contains two distinct integers whose nearest common ancestor is to be computed. Output Print exactly one line for each test case. The line should contain the integer that is the nearest common ancestor. Sample Input 2 16 1 14 8 5 10 16 5 9 4 6 8 4 4 10 1 13 6 15 10 11 6 7 10 2 16 3 8 1 16 12 16 7 5 2 3 3 4 3 1 1 5 3 5 Sample Output 4 3 Source Taejon 2002

# hihoCoder 1067-最近公共祖先·二

hihoCoder 1067-最近公共祖先·二 #1067 : 最近公共祖先·二 时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 上上回说到，小Hi和小Ho用非常拙劣——或者说粗糙的手段山寨出了一个神奇的网站，这个网站可以计算出某两个人的所有共同祖先中辈分最低的一个是谁。远在美国的他们利用了一些奇妙的技术获得了国内许多人的相关信息，并且搭建了一个小小的网站来应付来自四面八方的请求。 但正如我们所能想象到的……这样一个简单的算法并不能支撑住非常大的访问量，所以摆在小Hi和小Ho面前的无非两种选择： 其一是购买更为昂贵的服务器，通过提高计算机性能的方式来满足需求——但小Hi和小Ho并没有那么多的钱；其二则是改进他们的算法，通过提高计算机性能的利用率来满足需求——这个主意似乎听起来更加靠谱。 于是为了他们第一个在线产品的顺利运作，小Hi决定对小Ho进行紧急训练——好好的修改一番他们的算法。 而为了更好的向小Ho讲述这个问题，小Hi将这个问题抽象成了这个样子：假设现小Ho现在知道了N对父子关系——父亲和儿子的名字，并且这N对父子关系中涉及的所有人都拥有一个共同的祖先（这个祖先出现在这N对父子关系中），他需要对于小Hi的若干次提问——每次提问为两个人的名字（这两个人的名字在之前的父子关系中出现过），告诉小Hi这两个人的所有共同祖先中辈分最低的一个是谁？ 提示一：老老实实分情况讨论就不会出错的啦！ 提示二：并查集其实长得很像一棵树你们不觉得么？ 输入 每个测试点（输入文件）有且仅有一组测试数据。 每组测试数据的第1行为一个整数N，意义如前文所述。 每组测试数据的第2~N+1行，每行分别描述一对父子关系，其中第i+1行为两个由大小写字母组成的字符串Father_i, Son_i，分别表示父亲的名字和儿子的名字。 每组测试数据的第N+2行为一个整数M，表示小Hi总共询问的次数。 每组测试数据的第N+3~N+M+2行，每行分别描述一个询问，其中第N+i+2行为两个由大小写字母组成的字符串Name1_i, Name2_i，分别表示小Hi询问中的两个名字。 对于100%的数据，满足N<=10^5，M<=10^5, 且数据中所有涉及的人物中不存在两个名字相同的人（即姓名唯一的确定了一个人），所有询问中出现过的名字均在之前所描述的N对父子关系中出现过，第一个出现的名字所确定的人是其他所有人的公共祖先。 输出 对于每组测试数据，对于每个小Hi的询问，按照在输入中出现的顺序，各输出一行，表示查询的结果：他们的所有共同祖先中辈分最低的一个人的名字。 样例输入 4 Adam Sam Sam Joey Sam Micheal Adam Kevin 3 Sam Sam Adam Sam Micheal Kevin 样例输出 Sam Adam Adam

hihoCoder确实是个练习算法的好网站，之前我们写过朴素的最近公共祖先问题：hihoCoder Problem 1062: 最近公共祖先·一，但那是一个效率比较低的方法，这一次，hihoCoder详细给我们介绍了最近公共祖先的离线算法，而且讲解非常详细。 网站上的讲解详细，易于理解，我这里简单概括一下。所谓离线算法就是先把询问搜集起来，如果某个询问能先回答，则记录答案，直到把所有询问都解答了；与之相对的是在线算法，也就是每提出一个询问，我都要实时的马上回答。 离线算法综合了DFS和并查集。给定一个族谱（树形结构），我们先把每一个节点染成白色，并且在初始并查集中，每个点都是一个独立的集合，然后从树根开始深度优先遍历，当第一次经过某个节点a的时候，把它由白色改为灰色；如果第二次访问该节点的时候（也就是离开该点的时候），则把它由灰色改为黑色。 当a每次由白变灰之后，查看询问中是否出现过该节点，如果出现了，则查看询问中另一个节点b的颜色，如果b是灰色，则<a,b>的最近公共祖先就是b，因为b是灰色的，所以访问a之前肯定访问了b，所以它们的最近公共祖先是b；如果b是黑色，此时已经离开b了，并不能直接说明a和b的关系，但是<a,b>的最近公共祖先肯定在灰色链上，所以我们只要找出b向上的第一个灰色节点，就是<a,b>的最近公共祖先；如果b是白色，则说明b还没有访问，没有关于b的信息，所以我们暂时不管这个询问，等到访问到b时，a肯定不是白色，这是可以依据前两条规则得出它们的最近公共祖先。 当a每次由灰变黑之后，我们需要在并查集中将a和a的直接父节点合并UNION，因为当a由灰变黑时，a及其子树都访问结束了，但是a的直接父节点还没有访问结束，也就是说a的直接父节点还是灰色的，这样我们就记录了a向上的第一个灰色节点，这为上面的第二种情况判断做准备。 最近公共祖先的离线算法概括起来就是上面的内容，简单易懂也很强大。但是因为算法既包含DFS，又包含并查集，对初学者来说有一定的难度，而且这个题给出的数据是字符串形式的，数据量又很大，有很多细节需要注意。 我先把完整的代码贴出来，然后讲一下主要过程。 [cpp] #include<iostream> #include<string> #include<map> #include<vector> using namespace std; const int MAX_N=100010;//最大人数 map<string,int> name_index;//名字转换为数字 vector<string> index_name(MAX_N);//数字转换为名字 int color[MAX_N]={0};//0:白；1:灰；2:黑，初始颜色都是白色 int s_f[MAX_N];//son_father。s_f[i]表示第i个儿子的直接父亲 vector<vector<int> > f_s(MAX_N);//f_s[i]表示第i个父亲的所有孩子 vector<vector<int> > show_at(MAX_N);//show_at[i]表示第i个人在哪些询问里出现过 int q_l[MAX_N];//第i个询问的左边 int q_r[MAX_N];//第i个询问的右边 int father[MAX_N];//用于并查集，和s_f不一样 vector<string> ans;//最终结果 //保存某个人的信息，并返回其下标 int store_name(string name) { map<string,int>::iterator it=name_index.find(name); if(it==name_index.end())//还不存在 { int curr_index=name_index.size();//用当前已有人数作为其下标，正好是递增的。 name_index.insert(make_pair(name,curr_index)); index_name[curr_index]=name;//记录 father[curr_index]=curr_index;//初始的时候，并查集中每个元素都是一个独立的集合 return curr_index;//返回下标 } else return it->second;//已经存在，直接返回 } //并查集FIND操作 int find_father(int name) { return name==father[name]?name:(father[name]=find_father(father[name])); } //并查集UNION操作 void union_father(int name1,int name2) { father[find_father(name1)]=find_father(name2); } //深度遍历族谱树 void DFS(int root) { color[root]=1;//首先修改颜色为灰色 int show_time=show_at[root].size();//查看该元素是否在询问里出现 if(show_time!=0) { for(int i=0;i<show_time;i++)//判断所有询问 { int column=show_at[root][i]; int left=q_l[column];//找到该询问的左右元素 int right=q_r[column]; if(left==right)//如果是左右相同，则该自身即是其最近公共祖先 ans[column]=index_name[left]; else { if(left==root)//判断当前访问的是左边的还是右边的 { if(color[right]==1)//另一个点为灰色 ans[column]=index_name[right];//结果即为该灰色点 else if(color[right]=2)//另一个点为黑色 ans[column]=index_name[find_father(right)];//找其向上最近的灰色节点 } else { if(color[left]==1)//另一个点为灰色 ans[column]=index_name[left]; else if(color[left]=2)//另一个点为黑色 ans[column]=index_name[find_father(left)]; } } } } int sons=f_s[root].size();//查看是否有孩子节点 if(sons!=0) { for(int i=0;i<sons;i++) DFS(f_s[root][i]);//深度遍历其所有孩子 } color[root]=2;//改颜色为黑色 union_father(root,s_f[root]);//和直接父节点UNION } int main() { ios_base::sync_with_stdio(false);//取消同步，加速 cin.tie(0); //freopen("input.txt","r",stdin); int n,m; string name1,name2; int index1,index2; cin>>n; while(n–) { cin>>name1>>name2; index1=store_name(name1); index2=store_name(name2); f_s[index1].push_back(index2); s_f[index2]=index1; } cin>>m; ans.resize(m); for(int i=0;i<m;i++) { cin>>name1>>name2; index1=store_name(name1); index2=store_name(name2); q_l[i]=index1; q_r[i]=index2; show_at[index1].push_back(i); show_at[index2].push_back(i); } DFS(0); for(int i=0;i<m;i++) cout<<ans[i]<<endl; return 0; } [/cpp] 摆在我们面前的第一个问题就是数据的输入问题，题目给的每个人名都是字符串，当然我们可以直接用字符串构建一个树结构，然后进行查找、比较、赋值等操作，但是这样的时空效率都比较低，所以我们可以先用map<string,int> name_index和vector<string> index_name来记录人名字符串和人名数字下标，这样我们在DFS+并查集的时候可以只使用数字下标，到最后输出的时候再转换为字符串，提高效率。记录并返回人名数字下标的操作在函数int store_name(string name);中。 我们还需要记录父子关系，因为一个父亲可以有多个孩子，所以父亲-孩子关系需要用二维数组vector<vector<int> > f_s(MAX_N);来表示；而一个孩子只可能有一个父亲，所以孩子-父亲关系可以用一维数组int s_f[MAX_N];来表示。 还有两个数组需要初始化，每个节点的颜色初始化为白色，在并查集中每个节点单独为一个集合。 然后就是存储询问了。正如前面对LCA离线算法的描述，每当一个节点从白色变为灰色时，我们都要查看询问中是否出现过该节点。输入的询问中有很多节点，怎样来快速判断所有询问中是否有某个节点以及该询问中的另一个节点呢？如果这个问题处理不好，很可能就是TLE，反正我前两个版本都是因为这个原因TLE的。 这个问题可以通过两个步骤来解决，都是用空间来换时间。因为每一个询问都是由左右两个人名组成的，那么我们先把每次询问的左右两个人名记录在int q_l[MAX_N];和int q_r[MAX_N];中。然后还用一个二维数组vector<vector<int> > show_at(MAX_N);来记录某一个节点在哪些询问里出现过。这样当我们DFS到某个节点a时，首先查看show_at[a]这个数组是否为空，如果为空，说明a没有出现在任何一次询问中；如果不为空，则show_at[a]记录了a出现的所有询问的序号，根据这个序号，我们再去查q_l和q_r，这样就可以取出a出现时的那个询问的左右两个人名是什么了。所以整个过程只需要O(1)的时间，大大提高了时间效率。 因为题目中说明了

# hihoCoder 1062-最近公共祖先·一

hihoCoder 1062-最近公共祖先·一 #1062 : 最近公共祖先·一 时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 小Ho最近发现了一个神奇的网站！虽然还不够像58同城那样神奇，但这个网站仍然让小Ho乐在其中，但这是为什么呢？ “为什么呢？”小Hi如是问道，在他的观察中小Ho已经沉迷这个网站一周之久了，甚至连他心爱的树玩具都弃置一边。 “嘿嘿，小Hi，你快过来看！”小Ho招呼道。 “你看，在这个对话框里输入我的名字，在另一个对话框里，输入你的名字，再点这个查询按钮，就可以查出来……什么！我们居然有同一个祖祖祖祖祖爷爷？” “诶，真是诶……这个网站有点厉害啊。”小Hi不由感叹道。 “是啊，这是什么算法啊，这么厉害！”小Ho也附和道。 “别2，我说的是他能弄到这些数据很厉害，而人类的繁殖树这种层数比较浅的树对这类算法的要求可是简单的不得了，你都能写出来呢！”小Hi道。 “啊？我也能写出来？可是……该从哪开始呢？”小Ho困惑了。 小Ho要面临的问题是这样的，假设现在他知道了N个人的信息——他们的父亲是谁，他需要对于小Hi的每一次提问——两个人的名字，告诉小Hi这两个人的是否存在同一个祖先，如果存在，那么他们的所有共同祖先中辈分最低的一个是谁？ 提示：不着急，慢慢来，另外我有一个问题：挖掘机技术哪家强？！ 输入 每个测试点（输入文件）有且仅有一组测试数据。 每组测试数据的第1行为一个整数N，意义如前文所述。 每组测试数据的第2~N+1行，每行分别描述一对父子关系，其中第i+1行为两个由大小写字母组成的字符串Father_i, Son_i，分别表示父亲的名字和儿子的名字。 每组测试数据的第N+2行为一个整数M，表示小Hi总共询问的次数。 每组测试数据的第N+3~N+M+2行，每行分别描述一个询问，其中第N+i+2行为两个由大小写字母组成的字符串Name1_i, Name2_i，分别表示小Hi询问中的两个名字。 对于100%的数据，满足N<=10^2，M<=10^2, 且数据中所有涉及的人物中不存在两个名字相同的人（即姓名唯一的确定了一个人）。 输出 对于每组测试数据，对于每个小Hi的询问，输出一行，表示查询的结果：如果根据已知信息，可以判定询问中的两个人存在共同的祖先，则输出他们的所有共同祖先中辈分最低的一个人的名字，否则输出-1。 样例输入 11 JiaYan JiaDaihua JiaDaihua JiaFu JiaDaihua JiaJing JiaJing JiaZhen JiaZhen JiaRong JiaYuan JiaDaishan JiaDaishan JiaShe JiaDaishan JiaZheng JiaShe JiaLian JiaZheng JiaZhu JiaZheng JiaBaoyu 3 JiaBaoyu JiaLian JiaBaoyu JiaZheng JiaBaoyu LinDaiyu 样例输出 JiaDaishan JiaZheng -1