编写递归算法,在二叉树中求位于先序序列中第k个位置的结点的值
时间: 2023-04-23 22:05:51 浏览: 63
递归算法如下:
1. 如果树为空,返回空值。
2. 如果k等于1,返回根节点的值。
3. 否则,递归地在左子树中查找第k-1个位置的节点的值,如果找到了,返回该节点的值;否则,在右子树中查找第k-1-left_size个位置的节点的值,其中left_size是左子树的节点数。
代码实现如下:
```
int find_kth_node(TreeNode* root, int k) {
if (root == nullptr) {
return -1; // 返回空值
}
int left_size = count_nodes(root->left);
if (k == left_size + 1) {
return root->val; // 找到了第k个节点
} else if (k <= left_size) {
return find_kth_node(root->left, k); // 在左子树中查找
} else {
return find_kth_node(root->right, k - left_size - 1); // 在右子树中查找
}
}
int count_nodes(TreeNode* root) {
if (root == nullptr) {
return 0;
}
return 1 + count_nodes(root->left) + count_nodes(root->right);
}
```
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)