编写递归算法，在二叉树中求位于先序序列中第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;
}

相关问题

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

递归算法实现如下：

1. 如果根节点为空，返回空节点。
2. 如果k等于1，返回根节点。
3. 否则，递归遍历左子树，找到第k-1个节点。
4. 如果左子树中找到了第k-1个节点，返回该节点。
5. 否则，递归遍历右子树，找到第k-1-leftCount个节点。
6. 如果右子树中找到了第k-1-leftCount个节点，返回该节点。
7. 否则，返回空节点。

其中，leftCount表示左子树中的节点数。

代码实现如下：

public TreeNode findKthNode(TreeNode root, int k) {
    if (root == null) {
        return null;
    }
    int leftCount = countNodes(root.left);
    if (k == leftCount + 1) {
        return root;
    } else if (k <= leftCount) {
        return findKthNode(root.left, k);
    } else {
        return findKthNode(root.right, k - leftCount - 1);
    }
}

private int countNodes(TreeNode root) {
    if (root == null) {
        return ;
    }
    return 1 + countNodes(root.left) + countNodes(root.right);
}

编写递归算法，在二叉树中求位于先序序列中第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);
}