这道题目要求在给定的有根树中按照深

度优先遍历的顺序找到深度为h的第一个叶子节点。首先，我们需要构建一个树的数据结构来表示输入。可以使用一个数组或者链表来存储每个节点的父节点和子节点。 接下来，我们可以编写一个递归函数来进行深度优先遍历。函数将从根节点开始，并在每个节点处判断当前深度是否等于指定的深度h。如果是，则返回当前节点作为第一个叶子节点。如果不是，则继续递归遍历当前节点的子节点。

最后，我们可以调用该函数并输出结果。

整体思路如下：

1. 构建树的数据结构，可以使用数组或链表来存储每个节点的父节点和子节点。
2. 读取输入数据，构建树的结构。
3. 编写递归函数，传入当前节点、当前深度和指定深度h。
4. 在递归函数内部，判断当前节点的深度是否等于h并且没有子节点，满足条件则返回当前节点。
5. 遍历当前节点的子节点，对每个子节点进行递归调用。
6. 如果没有找到符合条件的叶子节点，则返回空值。
7. 调用递归函数并输出结果。

PY：

def find_first_leaf_node(tree, node, depth, h):
    # 如果当前节点的深度等于指定深度h，并且没有子节点，则返回当前节点
    if depth == h and len(tree[node]) == 0:
        return node
    
    # 递归遍历当前节点的子节点
    for child in tree[node]:
        leaf = find_first_leaf_node(tree, child, depth + 1, h)
        if leaf is not None:
            return leaf
    
    # 如果没有找到符合条件的叶子节点，则返回None
    return None


# 读取输入
n, h = map(int, input().split())
tree = {i: [] for i in range(1, n+1)}

for _ in range(n-1):
    u, v = map(int, input().split())
    tree[u].append(v)

# 调用函数并输出结果
first_leaf = find_first_leaf_node(tree, 1, 1, h)
print(first_leaf)

C++：

#include <iostream>
#include <vector>

using namespace std;

// 树节点结构体
struct TreeNode {
    int val;
    vector<TreeNode*> children;
    TreeNode(int x) : val(x) {}
};

// 深度优先遍历函数
int findFirstLeaf(TreeNode* root, int depth, int h) {
    // 如果当前节点的深度等于指定深度h，并且没有子节点，则返回当前节点值
    if (depth == h && root->children.empty()) {
        return root->val;
    }
    
    // 遍历当前节点的子节点并递归调用
    for (TreeNode* child : root->children) {
        int leaf = findFirstLeaf(child, depth + 1, h);
        if (leaf != -1) {
            return leaf;
        }
    }
    
    // 如果没有找到符合条件的叶子节点，则返回-1
    return -1;
}

int main() {
    int n, h;
    cin >> n >> h;
    
    // 构建树的数据结构
    vector<TreeNode*> nodes(n+1, nullptr);
    for (int i = 1; i <= n; i++) {
        nodes[i] = new TreeNode(i);
    }
    
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        nodes[u]->children.push_back(nodes[v]);
    }
    
    // 调用函数并输出结果
    int firstLeaf = findFirstLeaf(nodes[1], 1, h);
    cout << firstLeaf << endl;
    
    // 释放内存
    for (int i = 1; i <= n; i++) {
        delete nodes[i];
    }
    
    return 0;
}

本题需要在深度优先遍历时，计算当前节点的深度，并进行判断当前节点是否为深度为h的叶子，找到第一个叶子节点时，可以使用全局变量flag标记，结束dfs递归。

void dfs(int u)
{
    if(flag) return; //因为递归程序有很多分支，所以递归边界需要加上判断flag，否则会输出不同子树的多个叶子节点
    for (int i = 0; i < e[u].size(); i++)
    {
        int v = e[u][i];
        de[v] = de[u] + 1;
        //深度为h时，判断是否为叶子节点，并输出第一个叶子节点 
        if(de[v] == h && e[v].size()==0)
        {
            cout << e[u][i] <<" ";
            flag = true;
            return;
	}
	//因为只需要找到h层的第一个叶子节点，所以只需要在深度小于h时进行深度优先遍历
	if(de[v] < h)
            dfs(v);
    }
}

#include <bits/stdc++.h>
using namespace std;
bool flag = 0;/*用于标记是否已出现
第一个符合条件的叶子节点 */ 
vector<int> e[1005];
int n,h;
int de[1005];
void dfs(int u);//声明 
int main()
{
	cin >> n >> h;
	for (int i = 1;i <= n - 1;i++)
	{
		int U,V;
		cin >> U >> V;
		e[U].push_back(V);//fa[]没必要 
	}
	de[1] = 1;//初始深度 
	dfs(1);
	return 0;
}
void dfs (int u)
{
	for (int i = 0;i < (int)e[u].size();i++)
	{
		int v = e[u][i];
		de[v] = de[u]+1;//计算深度 
		if (de[v] == h && e[v].size() == 0 && flag == 0)//判断是否符合题意 
		{
			cout << v;//输出 
			flag = 1; 
			
		}
		dfs(v);//继续下去 
	}
	return;
}

已AC，请谨慎使用，c++14(O2)

只要枚举就可以了。

核心代码：

void dfs(int u,int cnt){
    if(cnt==h)
        if(e[u].size()==0){
            cout<<u;
            exit(0);  //退出
        }
    for(int i=0;i<e[u].size();i++){
        int v=e[u][i];
        dfs(v,cnt+1); //枚举
    }
}