编写递归算法在二叉树中求位于先序序列中第k个位置的结点的值

在二叉树中，通过递归算法找到先序遍历序列中的第k个节点，可以采用自顶向下的策略。以下是递归解决方案：

1. **基本情况**：如果二叉树为空或者k等于0，说明我们已经找到了序列的第一个元素，返回null（如果是查找第一个节点）或返回0（对于空树）。

2. **递归步骤**：对于非空树T，
- 先访问根节点root，并将k减一（因为我们按照先序遍历顺序，首先访问根节点）。
- 如果k仍然大于0，那么继续在左子树（`T.left`）中递归寻找，直到k为0。
- 否则，k变成负数，所以在右子树（`T.right`）中递归寻找，因为先序遍历时左子树在根节点之前。

递归伪代码示例：

def find_kth_node_in_preorder(root, k):
    if root is None or k == 0:
        return root.value if k == 0 else None
    k -= 1
    left_result = find_kth_node_in_preorder(root.left, k)
    if left_result is not None:
        return left_result
    return find_kth_node_in_preorder(root.right, k + 1)

相关问题

编写递归算法，在二叉树中求位于先序序列中第k个位置的结点的值

递归算法如下：

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);
}

编写递归算法，在二叉树中求位于先序序列中第k个位置的结点

递归算法如下：

1. 如果树为空，返回空节点。
2. 如果当前节点是第k个节点，返回当前节点。
3. 否则，递归遍历左子树，返回左子树中第k个节点。
4. 如果左子树中没有第k个节点，递归遍历右子树，返回右子树中第k-left-1个节点（left为左子树节点数）。

代码实现如下：

TreeNode* findKthNode(TreeNode* root, int k) {
    if (root == nullptr) {
        return nullptr;
    }
    int leftCount = countNodes(root->left);
    if (leftCount + 1 == k) {
        return root;
    } else if (leftCount >= k) {
        return findKthNode(root->left, k);
    } else {
        return findKthNode(root->right, k - leftCount - 1);
    }
}

int countNodes(TreeNode* root) {
    if (root == nullptr) {
        return ;
    }
    return countNodes(root->left) + countNodes(root->right) + 1;
}